Graphs: BFS & DFS

from collections import deque


def build_graph(n: int, edges: list[list[int]]) -> list[list[int]]:
    """Adjacency list for an undirected graph with nodes 0..n-1. Each node's
    neighbors keep the order the edges were given, which fixes the visit order."""
    graph: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)  # Undirected: store the edge in both directions.
    return graph


def bfs_order(graph: list[list[int]], start: int) -> list[int]:
    """Nodes in the order breadth-first search reaches them from `start`."""
    seen = [False] * len(graph)
    order = []
    queue = deque([start])
    seen[start] = True
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if not seen[neighbor]:
                seen[neighbor] = True  # Mark on enqueue so no node is queued twice.
                queue.append(neighbor)
    return order


def dfs_order(graph: list[list[int]], start: int) -> list[int]:
    """Nodes in the order a recursive depth-first search reaches them from `start`."""
    seen = [False] * len(graph)
    order: list[int] = []
    dfs_visit(graph, start, seen, order)
    return order


def dfs_visit(graph: list[list[int]], node: int, seen: list[bool], order: list[int]) -> None:
    seen[node] = True
    order.append(node)
    for neighbor in graph[node]:
        # Go all the way down this neighbor before trying the next one.
        if not seen[neighbor]:
            dfs_visit(graph, neighbor, seen, order)


def dfs_order_iterative(graph: list[list[int]], start: int) -> list[int]:
    """The same order as dfs_order, with your own stack in place of the call stack."""
    seen = [False] * len(graph)
    order: list[int] = []
    stack = [start]
    while stack:
        node = stack.pop()
        # A node can wait on the stack more than once. Visit only the first copy popped.
        if seen[node]:
            continue
        # Mark on pop, not on push. A node pushed early may be reached again from
        # deeper down, and recursion would visit it from there.
        seen[node] = True
        order.append(node)
        # Push neighbors in reverse, so the first one comes off the stack first.
        for neighbor in reversed(graph[node]):
            if not seen[neighbor]:
                stack.append(neighbor)
    return order


def bfs_distances(graph: list[list[int]], start: int) -> list[int]:
    """Fewest edges from `start` to every node, or -1 where no path exists."""
    dist = [-1] * len(graph)  # -1 also means "not seen yet".
    dist[start] = 0
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if dist[neighbor] == -1:
                # BFS reaches nodes in order of distance, so the first visit is the shortest.
                dist[neighbor] = dist[node] + 1
                queue.append(neighbor)
    return dist


if __name__ == "__main__":
    graph = build_graph(7, [[0, 1], [0, 3], [1, 2], [3, 4], [2, 5], [4, 5]])
    print(bfs_order(graph, 0))  # [0, 1, 3, 2, 4, 5]
    print(dfs_order(graph, 0))  # [0, 1, 2, 5, 4, 3]
    print(dfs_order_iterative(graph, 0))  # [0, 1, 2, 5, 4, 3]
    print(bfs_distances(graph, 0))  # [0, 1, 2, 1, 2, 3, -1]

// Adjacency list for an undirected graph with nodes 0..n-1. Each node's
// neighbors keep the order the edges were given, which fixes the visit order.
export function buildGraph(n: number, edges: number[][]): number[][] {
  const graph: number[][] = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u); // Undirected: store the edge in both directions.
  }
  return graph;
}

// Nodes in the order breadth-first search reaches them from start.
export function bfsOrder(graph: number[][], start: number): number[] {
  const seen = new Array<boolean>(graph.length).fill(false);
  const order: number[] = [];
  const queue = [start];
  seen[start] = true;
  let head = 0; // Dequeue by moving a head index, because shift() is O(n).
  while (head < queue.length) {
    const node = queue[head++];
    order.push(node);
    for (const neighbor of graph[node]) {
      if (!seen[neighbor]) {
        seen[neighbor] = true; // Mark on enqueue so no node is queued twice.
        queue.push(neighbor);
      }
    }
  }
  return order;
}

// Nodes in the order a recursive depth-first search reaches them from start.
export function dfsOrder(graph: number[][], start: number): number[] {
  const seen = new Array<boolean>(graph.length).fill(false);
  const order: number[] = [];
  dfsVisit(graph, start, seen, order);
  return order;
}

function dfsVisit(graph: number[][], node: number, seen: boolean[], order: number[]): void {
  seen[node] = true;
  order.push(node);
  for (const neighbor of graph[node]) {
    // Go all the way down this neighbor before trying the next one.
    if (!seen[neighbor]) dfsVisit(graph, neighbor, seen, order);
  }
}

// The same order as dfsOrder, with your own stack in place of the call stack.
export function dfsOrderIterative(graph: number[][], start: number): number[] {
  const seen = new Array<boolean>(graph.length).fill(false);
  const order: number[] = [];
  const stack = [start];
  while (stack.length > 0) {
    const node = stack.pop()!;
    // A node can wait on the stack more than once. Visit only the first copy popped.
    if (seen[node]) continue;
    // Mark on pop, not on push. A node pushed early may be reached again from
    // deeper down, and recursion would visit it from there.
    seen[node] = true;
    order.push(node);
    // Push neighbors in reverse, so the first one comes off the stack first.
    for (let i = graph[node].length - 1; i >= 0; i--) {
      const neighbor = graph[node][i];
      if (!seen[neighbor]) stack.push(neighbor);
    }
  }
  return order;
}

// Fewest edges from start to every node, or -1 where no path exists.
export function bfsDistances(graph: number[][], start: number): number[] {
  const dist = new Array<number>(graph.length).fill(-1); // -1 also means "not seen yet".
  dist[start] = 0;
  const queue = [start];
  let head = 0;
  while (head < queue.length) {
    const node = queue[head++];
    for (const neighbor of graph[node]) {
      if (dist[neighbor] === -1) {
        // BFS reaches nodes in order of distance, so the first visit is the shortest.
        dist[neighbor] = dist[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return dist;
}

const graph = buildGraph(7, [[0, 1], [0, 3], [1, 2], [3, 4], [2, 5], [4, 5]]);
console.log(JSON.stringify(bfsOrder(graph, 0))); // [0,1,3,2,4,5]
console.log(JSON.stringify(dfsOrder(graph, 0))); // [0,1,2,5,4,3]
console.log(JSON.stringify(dfsOrderIterative(graph, 0))); // [0,1,2,5,4,3]
console.log(JSON.stringify(bfsDistances(graph, 0))); // [0,1,2,1,2,3,-1]

package main

import "fmt"

// buildGraph returns the adjacency list for an undirected graph with nodes
// 0..n-1. Each node's neighbors keep the order the edges were given, which
// fixes the visit order.
func buildGraph(n int, edges [][]int) [][]int {
	graph := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u) // Undirected: store the edge in both directions.
	}
	return graph
}

// bfsOrder returns nodes in the order breadth-first search reaches them from start.
func bfsOrder(graph [][]int, start int) []int {
	seen := make([]bool, len(graph))
	order := []int{}
	queue := []int{start}
	seen[start] = true
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)
		for _, neighbor := range graph[node] {
			if !seen[neighbor] {
				seen[neighbor] = true // Mark on enqueue so no node is queued twice.
				queue = append(queue, neighbor)
			}
		}
	}
	return order
}

// dfsOrder returns nodes in the order a recursive depth-first search reaches
// them from start.
func dfsOrder(graph [][]int, start int) []int {
	seen := make([]bool, len(graph))
	return dfsVisit(graph, start, seen, []int{})
}

func dfsVisit(graph [][]int, node int, seen []bool, order []int) []int {
	seen[node] = true
	order = append(order, node)
	for _, neighbor := range graph[node] {
		// Go all the way down this neighbor before trying the next one.
		if !seen[neighbor] {
			order = dfsVisit(graph, neighbor, seen, order)
		}
	}
	return order
}

// dfsOrderIterative returns the same order as dfsOrder, using your own stack
// in place of the call stack.
func dfsOrderIterative(graph [][]int, start int) []int {
	seen := make([]bool, len(graph))
	order := []int{}
	stack := []int{start}
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		// A node can wait on the stack more than once. Visit only the first copy popped.
		if seen[node] {
			continue
		}
		// Mark on pop, not on push. A node pushed early may be reached again from
		// deeper down, and recursion would visit it from there.
		seen[node] = true
		order = append(order, node)
		// Push neighbors in reverse, so the first one comes off the stack first.
		for i := len(graph[node]) - 1; i >= 0; i-- {
			neighbor := graph[node][i]
			if !seen[neighbor] {
				stack = append(stack, neighbor)
			}
		}
	}
	return order
}

// bfsDistances returns the fewest edges from start to every node, or -1 where
// no path exists.
func bfsDistances(graph [][]int, start int) []int {
	dist := make([]int, len(graph))
	for i := range dist {
		dist[i] = -1 // -1 also means "not seen yet".
	}
	dist[start] = 0
	queue := []int{start}
	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		for _, neighbor := range graph[node] {
			if dist[neighbor] == -1 {
				// BFS reaches nodes in order of distance, so the first visit is the shortest.
				dist[neighbor] = dist[node] + 1
				queue = append(queue, neighbor)
			}
		}
	}
	return dist
}

func main() {
	graph := buildGraph(7, [][]int{{0, 1}, {0, 3}, {1, 2}, {3, 4}, {2, 5}, {4, 5}})
	fmt.Println(bfsOrder(graph, 0))          // [0 1 3 2 4 5]
	fmt.Println(dfsOrder(graph, 0))          // [0 1 2 5 4 3]
	fmt.Println(dfsOrderIterative(graph, 0)) // [0 1 2 5 4 3]
	fmt.Println(bfsDistances(graph, 0))      // [0 1 2 1 2 3 -1]
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Adjacency list for an undirected graph with nodes 0..n-1. Each node's
    // neighbors keep the order the edges were given, which fixes the visit order.
    public static List<List<int>> BuildGraph(int n, int[][] edges)
    {
        var graph = new List<List<int>>();
        for (int i = 0; i < n; i++) graph.Add(new List<int>());
        foreach (var edge in edges)
        {
            int u = edge[0], v = edge[1];
            graph[u].Add(v);
            graph[v].Add(u); // Undirected: store the edge in both directions.
        }
        return graph;
    }

    // Nodes in the order breadth-first search reaches them from start.
    public static List<int> BfsOrder(List<List<int>> graph, int start)
    {
        var seen = new bool[graph.Count];
        var order = new List<int>();
        var queue = new Queue<int>();
        queue.Enqueue(start);
        seen[start] = true;
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            order.Add(node);
            foreach (int neighbor in graph[node])
            {
                if (!seen[neighbor])
                {
                    seen[neighbor] = true; // Mark on enqueue so no node is queued twice.
                    queue.Enqueue(neighbor);
                }
            }
        }
        return order;
    }

    // Nodes in the order a recursive depth-first search reaches them from start.
    public static List<int> DfsOrder(List<List<int>> graph, int start)
    {
        var seen = new bool[graph.Count];
        var order = new List<int>();
        DfsVisit(graph, start, seen, order);
        return order;
    }

    static void DfsVisit(List<List<int>> graph, int node, bool[] seen, List<int> order)
    {
        seen[node] = true;
        order.Add(node);
        foreach (int neighbor in graph[node])
        {
            // Go all the way down this neighbor before trying the next one.
            if (!seen[neighbor]) DfsVisit(graph, neighbor, seen, order);
        }
    }

    // The same order as DfsOrder, with your own stack in place of the call stack.
    public static List<int> DfsOrderIterative(List<List<int>> graph, int start)
    {
        var seen = new bool[graph.Count];
        var order = new List<int>();
        var stack = new Stack<int>();
        stack.Push(start);
        while (stack.Count > 0)
        {
            int node = stack.Pop();
            // A node can wait on the stack more than once. Visit only the first copy popped.
            if (seen[node]) continue;
            // Mark on pop, not on push. A node pushed early may be reached again from
            // deeper down, and recursion would visit it from there.
            seen[node] = true;
            order.Add(node);
            // Push neighbors in reverse, so the first one comes off the stack first.
            for (int i = graph[node].Count - 1; i >= 0; i--)
            {
                int neighbor = graph[node][i];
                if (!seen[neighbor]) stack.Push(neighbor);
            }
        }
        return order;
    }

    // Fewest edges from start to every node, or -1 where no path exists.
    public static int[] BfsDistances(List<List<int>> graph, int start)
    {
        var dist = new int[graph.Count];
        Array.Fill(dist, -1); // -1 also means "not seen yet".
        dist[start] = 0;
        var queue = new Queue<int>();
        queue.Enqueue(start);
        while (queue.Count > 0)
        {
            int node = queue.Dequeue();
            foreach (int neighbor in graph[node])
            {
                if (dist[neighbor] == -1)
                {
                    // BFS reaches nodes in order of distance, so the first visit is the shortest.
                    dist[neighbor] = dist[node] + 1;
                    queue.Enqueue(neighbor);
                }
            }
        }
        return dist;
    }

    public static void Main()
    {
        var graph = BuildGraph(7, [[0, 1], [0, 3], [1, 2], [3, 4], [2, 5], [4, 5]]);
        Console.WriteLine(Format(BfsOrder(graph, 0))); // [0, 1, 3, 2, 4, 5]
        Console.WriteLine(Format(DfsOrder(graph, 0))); // [0, 1, 2, 5, 4, 3]
        Console.WriteLine(Format(DfsOrderIterative(graph, 0))); // [0, 1, 2, 5, 4, 3]
        Console.WriteLine(Format(BfsDistances(graph, 0))); // [0, 1, 2, 1, 2, 3, -1]
    }

    static string Format(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    // Adjacency list for an undirected graph with nodes 0..n-1. Each node's
    // neighbors keep the order the edges were given, which fixes the visit order.
    static List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.get(u).add(v);
            graph.get(v).add(u); // Undirected: store the edge in both directions.
        }
        return graph;
    }

    // Nodes in the order breadth-first search reaches them from start.
    static List<Integer> bfsOrder(List<List<Integer>> graph, int start) {
        boolean[] seen = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        seen[start] = true;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            order.add(node);
            for (int neighbor : graph.get(node)) {
                if (!seen[neighbor]) {
                    seen[neighbor] = true; // Mark on enqueue so no node is queued twice.
                    queue.add(neighbor);
                }
            }
        }
        return order;
    }

    // Nodes in the order a recursive depth-first search reaches them from start.
    static List<Integer> dfsOrder(List<List<Integer>> graph, int start) {
        boolean[] seen = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        dfsVisit(graph, start, seen, order);
        return order;
    }

    static void dfsVisit(List<List<Integer>> graph, int node, boolean[] seen, List<Integer> order) {
        seen[node] = true;
        order.add(node);
        for (int neighbor : graph.get(node)) {
            // Go all the way down this neighbor before trying the next one.
            if (!seen[neighbor]) dfsVisit(graph, neighbor, seen, order);
        }
    }

    // The same order as dfsOrder, with your own stack in place of the call stack.
    static List<Integer> dfsOrderIterative(List<List<Integer>> graph, int start) {
        boolean[] seen = new boolean[graph.size()];
        List<Integer> order = new ArrayList<>();
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            // A node can wait on the stack more than once. Visit only the first copy popped.
            if (seen[node]) continue;
            // Mark on pop, not on push. A node pushed early may be reached again from
            // deeper down, and recursion would visit it from there.
            seen[node] = true;
            order.add(node);
            // Push neighbors in reverse, so the first one comes off the stack first.
            List<Integer> neighbors = graph.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int neighbor = neighbors.get(i);
                if (!seen[neighbor]) stack.push(neighbor);
            }
        }
        return order;
    }

    // Fewest edges from start to every node, or -1 where no path exists.
    static int[] bfsDistances(List<List<Integer>> graph, int start) {
        int[] dist = new int[graph.size()];
        Arrays.fill(dist, -1); // -1 also means "not seen yet".
        dist[start] = 0;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int node = queue.poll();
            for (int neighbor : graph.get(node)) {
                if (dist[neighbor] == -1) {
                    // BFS reaches nodes in order of distance, so the first visit is the shortest.
                    dist[neighbor] = dist[node] + 1;
                    queue.add(neighbor);
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 3}, {1, 2}, {3, 4}, {2, 5}, {4, 5}};
        List<List<Integer>> graph = buildGraph(7, edges);
        System.out.println(bfsOrder(graph, 0)); // [0, 1, 3, 2, 4, 5]
        System.out.println(dfsOrder(graph, 0)); // [0, 1, 2, 5, 4, 3]
        System.out.println(dfsOrderIterative(graph, 0)); // [0, 1, 2, 5, 4, 3]
        System.out.println(Arrays.toString(bfsDistances(graph, 0))); // [0, 1, 2, 1, 2, 3, -1]
    }
}