BFS & DFS — Graph Traversals

Graph traversal algorithms visit every reachable vertex from a starting node, and they underpin almost everything you do with graphs: pathfinding, connectivity, cycle detection, and ordering. Two fundamental strategies exist:

• BFS explores the graph level by level — all distance-1 nodes, then all distance-2, and so on.
• DFS explores as deep as possible along each branch before backtracking.

Both run in O(V + E) time — every vertex and edge is touched at most once — so the choice between them is about order and memory, not asymptotic cost.

Breadth-First Search (BFS)

BFS is driven by a queue (FIFO): dequeue a vertex, enqueue its undiscovered neighbors. The order vertices leave the queue is the level order.

Graph: A — B — C
       |       |
       D ————— E

BFS from A: A → B → D → C → E
        (level 0) (level 1) (level 2)

Because it expands one complete level before the next, BFS finds the shortest path in edges in unweighted graphs — the first time a vertex is discovered, it is via a minimum-hop route.

BFS(s):
  queue = [s]; mark s visited
  while queue not empty:
    u = dequeue
    for v in neighbors(u):
      if v not visited:
        mark v visited; parent[v] = u; enqueue v

Applications: shortest path in unweighted graphs, connected components, web crawling, “degrees of separation”, and flooding/broadcast protocols.

Depth-First Search (DFS)

DFS is driven by a stack (LIFO) — or by recursion, which uses the call stack for free. It follows one path to a dead end, then backtracks to the most recent vertex with unexplored edges.

DFS from A: A → B → C → E → D

DFS(u):
  mark u visited
  for v in neighbors(u):
    if v not visited: DFS(v)

The finish order — the reverse of the order in which vertices are “done” — is the basis for topological sort. A back edge (an edge to a still-active vertex) is exactly a cycle. Applications: cycle detection, topological ordering of DAGs, strongly connected components (Tarjan/Kosaraju), maze solving, dependency resolution.

Visited Tracking: Do It Once

Both algorithms must mark vertices visited at discovery, not at processing — otherwise a cyclic graph revisits vertices forever and a dense graph blows up to exponential time. The visited set also makes disconnected graphs tractable: wrap the traversal in an outer loop over all vertices, restarting at each unvisited one. That single loop turns one-component traversal into connected-components discovery.

Iterative vs Recursive DFS

Recursive is usually clearer; iterative removes the overflow ceiling. Both are O(V + E).

Choosing Between BFS and DFS

Topological Sort: DFS vs Kahn’s

A topological order is a linear ordering of a DAG where every edge points forward.

• DFS-based: run DFS, record finish times, output vertices in reverse finish order. Elegant, and it doubles as cycle detection — a back edge means the graph is not a DAG.
• Kahn’s algorithm: repeatedly remove vertices with in-degree 0, appending them to the output and decrementing neighbors’ in-degrees. Iterative and dependency-driven; if it cannot remove all vertices, a cycle exists.

Use Kahn’s when you want a stable, dependency-driven order (build systems); use DFS when you also need traversal metadata such as SCCs.

Worked Example

Traverse the graph below from A with neighbor lists ordered alphabetically:

        A
       / \
      B   C
     / \   \
    D   E   F

BFS from A:  A, B, C, D, E, F
DFS from A:  A, B, D, E, C, F

Both visit all 6 vertices and 5 edges — O(V + E) = O(11); only the order differs. BFS proves A→F is two edges (A–C–F). DFS finishes E before D and C before F — reverse finish order F, C, E, D, B, A is a valid topological order when edges point parent → child.

Practice Trajectory

1. Hand-trace BFS and DFS on a 7-vertex graph and write out the exact visit order from a fixed neighbor order.
2. Implement both iteratively with explicit visited sets; run them on a graph with a cycle to confirm termination.
3. Add the outer all-vertices loop and count connected components in a disconnected graph.
4. Implement DFS cycle detection (track vertices on the current recursion path) and verify it on a DAG vs a cyclic graph.
5. Implement both DFS-based and Kahn’s topological sort on the same DAG and check that each produces a valid order.

When It’s the Right Tool