Graph Traversal: BFS and DFS

Graph traversal means systematically visiting vertices reachable from a starting point. The two core tools are breadth-first search (BFS) and depth-first search (DFS).

Breadth-first search

BFS explores level by level from a source. It uses a queue: push the source, pop the oldest vertex, then push each unvisited neighbor.

BFS(adj, src):
    mark src visited
    push src into queue
    while queue not empty:
        u = pop front
        visit u
        for each v in adj[u]:
            if v is unvisited:
                mark v visited
                push v

Because BFS visits by increasing number of edges, it finds shortest paths in unweighted graphs.

Depth-first search

DFS goes as deep as possible before backtracking. It can be written with recursion or with an explicit stack.

DFS(u):
    mark u visited
    visit u
    for each v in adj[u]:
        if v is unvisited:
            DFS(v)

The iterative version uses a stack. Push neighbors in reverse order if you want the same order as recursive DFS on a normally ordered adjacency list.

Connected components

To count connected components in an undirected graph, start a BFS or DFS from every unvisited vertex. Each new start discovers one component.

Cycle detection

For an undirected graph, DFS tracks the parent. Seeing a visited neighbor that is not the parent means a cycle exists.

For a directed graph, use colors: white = unvisited, gray = currently in recursion stack, black = fully processed. Finding an edge to gray means a cycle.

Topological sort

A topological ordering places every directed edge u -> v with u before v. It exists only for DAGs. DFS can produce it by pushing each vertex after all outgoing neighbors finish.

Kahn's algorithm is the BFS-like alternative: compute in-degrees, repeatedly pop vertices with in-degree 0, and decrement their outgoing neighbors.

Shortest path in an unweighted graph

BFS can also record distance and parent arrays.

Grids as graphs: flood fill and islands

A grid cell can be a vertex. Edges connect up, down, left, and right neighbors.

A number-of-islands solution starts BFS from every unvisited land cell and marks its whole component.

Challenge: BFS from source

Challenge: Number of connected components

Challenge: Number of islands

Check your understanding