Graph Algorithms

Graph Traversal: BFS & DFS

The two fundamental ways to visit every reachable vertex of a graph — BFS explores in layers and finds shortest paths by edge count, DFS dives as deep as possible and reveals structure like cycles and components.

BFS: FIFO queue, visits vertices in order of distance — the shortest path in an unweighted graph
DFS: LIFO stack (explicit or via recursion), visits as deep as possible before backtracking
Both run in O(V + E) with an adjacency list — every vertex and edge touched once
DFS preorder/postorder timestamps power Topological Sort and Strongly Connected Components
Recursive DFS risks StackOverflowError on long chains (e.g. a linked-list-shaped graph with 100,000 nodes) — an explicit stack avoids the recursion depth limit

BFS — shortest path by edge count

static int[] bfs(List<List<Integer>> adj, int source) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);
    dist[source] = 0;
    Deque<Integer> queue = new ArrayDeque<>();
    queue.add(source);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        for (int v : adj.get(u)) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue.add(v);
            }
        }
    }
    return dist;
}

DFS — recursive, with a visited set

static void dfs(List<List<Integer>> adj, int u, boolean[] visited, List<Integer> order) {
    visited[u] = true;
    order.add(u);                       // preorder: process on the way down
    for (int v : adj.get(u)) {
        if (!visited[v]) dfs(adj, v, visited, order);
    }
    // a second append here would record postorder — used by topological sort
}

BFS vs DFS
	BFS	DFS
Data structure	queue	stack (or recursion)
Finds	shortest path (unweighted), level order	connectivity, cycles, topological order
Memory shape	O(width) of the frontier	O(depth) of the recursion
Typical use	shortest path, bipartiteness check	cycle detection, SCCs, backtracking-style search