Graph Traversals

BFS and DFS are the two engines that almost every graph algorithm runs on top of. Connected components, shortest path on unweighted graphs, cycle detection, topological sort, bipartite checking, flood fill, Dijkstra (a weighted BFS), Kruskal's MST (sort + Union-Find on edges) — all of them are 5–20 line variants of one of these two patterns. Master them and most graph problems collapse into "which one and what do I track?".

What BFS and DFS Actually Are

Both visit every reachable vertex exactly once, in O(V + E). The only difference: what data structure decides the next vertex to process.

• BFS uses a queue (FIFO) → explores level by level.
• DFS uses a stack (LIFO) → explores one branch all the way down, then backtracks.

That single swap changes everything: shortest paths, memory profile, the set of problems each is good at.

` 1 / \ BFS order: 1, 2, 3, 4, 5, 6, 7 2 3 DFS order: 1, 2, 4, 5, 3, 6, 7 / \ / \ 4 5 6 7 `

Daily Mental Model

• BFS = a flood spreading outward from a source — every wave reaches the next ring of cells before going further.
• DFS = exploring a maze with one hand on the wall — go as deep as you can, hit a dead end, back up to the last fork, try the next option.

Once you can predict which one a problem wants from one or two key words ("shortest", "level", "all paths", "cycle"), recognising graph problems becomes mechanical.

Beginner Mistakes to Skip

1. Forgetting the visited set on a graph with cycles. BFS/DFS without it loops forever. Trees don't need it; general graphs always do. 2. Marking visited at pop time instead of push time in BFS. A vertex can end up enqueued multiple times by different neighbours before it's processed → wasted work and wrong distances. Mark visited the moment you push. 3. Recursive DFS on a 100k-deep graph. JS / Java / Python all blow the call stack around ~10⁴–10⁵ frames. Use an explicit stack for deep graphs. 4. Using DFS for shortest path on an unweighted graph. DFS finds *some* path, not the shortest. Use BFS. 5. Using BFS for cycle detection on a directed graph and trying the "neighbour-not-parent" trick. That trick only works on undirected graphs. Directed graphs need DFS with WHITE/GRAY/BLACK colors (or Kahn's BFS). 6. Dequeueing with \shift()\ on a JS array. That's O(n) per pop and turns your O(V+E) BFS into O(V·E). Use a head index with a regular array, or a real deque library.

Intermediate: BFS Template You'll Use Forever

`js function bfs(adj, start) { const visited = new Set([start]); const dist = new Map([[start, 0]]); const q = [start]; let head = 0; // O(1) "dequeue" while (head < q.length) { const u = q[head++]; for (const v of adj[u]) { if (visited.has(v)) continue; visited.add(v); dist.set(v, dist.get(u) + 1); q.push(v); } } return dist; } `

Three things to internalise:

• Mark visited when pushing, not when popping.
• The distance you record on the first visit is the shortest distance (in edges).
• Total work is O(V+E) — every vertex is pushed once, every edge inspected twice in undirected graphs.

Intermediate: DFS Two Ways

Recursive (clean, but stack-bound):

`js function dfs(adj, u, visited = new Set()) { visited.add(u); for (const v of adj[u]) { if (!visited.has(v)) dfs(adj, v, visited); } } `

Iterative with an explicit stack:

`js function dfsIter(adj, start) { const visited = new Set(); const stack = [start]; while (stack.length) { const u = stack.pop(); if (visited.has(u)) continue; visited.add(u); for (const v of adj[u]) { if (!visited.has(v)) stack.push(v); } } } `

Subtle: in the iterative version we mark visited at pop time (not push) because a vertex may be pushed many times before any of those copies pops. Pre-checking on push is also valid and slightly more efficient — pick one and be consistent.

Intermediate: BFS vs DFS — Which One Does the Problem Want?

Signal in the problem	Use
"shortest", "minimum number of steps", unweighted	BFS
"all paths", "permutations", "combinations"	DFS + backtracking
"any path / does a path exist?"	either
"cycle in directed graph"	DFS (3-color) or BFS (Kahn)
"topological sort"	DFS post-order or BFS (Kahn)
"level by level"	BFS
"deep recursion natural" (trees)	DFS
"find connected components"	either — DFS is one line shorter
"memory tight on a wide graph"	DFS (O(depth) vs O(width))
"memory tight on a deep graph"	BFS (O(width) vs O(depth))

The space situation flips depending on shape — that's worth remembering. A balanced tree has ~n/2 leaves, so BFS holds half the tree at the bottom level. DFS only holds one root-to-leaf path.

Intermediate: Connected Components, Bipartite Check, Cycle Detection

Connected components (undirected): outer loop over all vertices; on each unvisited vertex, launch a BFS/DFS and increment a counter.

Bipartite check: BFS with two colors. Color the start vertex 0; color every neighbour the opposite color. If you ever try to color a visited vertex the *same* color as its source, the graph is not bipartite. Equivalent statement: the graph has an odd cycle.

Cycle detection in undirected graphs: DFS while remembering the parent. If you reach a visited neighbour that isn't the parent, you've found a back-edge → cycle. Or use Union-Find on edges and detect when both endpoints are already in the same set.

Advanced: Topological Sort — Two Algorithms, One Problem

A linear ordering of a DAG's vertices such that every edge \u → v\ goes left-to-right.

DFS post-order method (Tarjan-style):

`js function topoDFS(V, adj) { const visited = new Set(), order = []; function dfs(u) { visited.add(u); for (const v of adj[u]) if (!visited.has(v)) dfs(v); order.push(u); // push AFTER visiting all descendants } for (let u = 0; u < V; u++) if (!visited.has(u)) dfs(u); return order.reverse(); } `

Kahn's BFS algorithm (in-degree based):

`js function topoKahn(V, adj) { const indeg = Array(V).fill(0); for (let u = 0; u < V; u++) for (const v of adj[u]) indeg[v]++; const q = [], order = []; for (let u = 0; u < V; u++) if (indeg[u] === 0) q.push(u); let head = 0; while (head < q.length) { const u = q[head++]; order.push(u); for (const v of adj[u]) if (--indeg[v] === 0) q.push(v); } return order.length === V ? order : null; // null ⇒ cycle exists } `

Why Kahn's also detects cycles: if any vertex still has in-degree > 0 after the queue empties, it sits in a cycle and could never reach in-degree 0. Course-schedule problems are this exact algorithm.

Advanced: Cycle Detection in Directed Graphs — the 3-Color DFS

`js const WHITE = 0, GRAY = 1, BLACK = 2; function hasCycle(V, adj) { const color = Array(V).fill(WHITE); function dfs(u) { color[u] = GRAY; // entered, not yet finished for (const v of adj[u]) { if (color[v] === GRAY) return true; // back edge → cycle if (color[v] === WHITE && dfs(v)) return true; } color[u] = BLACK; // fully processed return false; } for (let u = 0; u < V; u++) if (color[u] === WHITE && dfs(u)) return true; return false; } `

GRAY = "currently on the recursion path". The instant DFS sees a GRAY vertex, that edge closes a cycle.

Advanced: Multi-Source BFS — One BFS, Many Starting Points

If the problem says "find the distance from each cell to the nearest of these k sources", don't run k separate BFSes. Push all sources into the initial queue at distance 0; the first time BFS visits any cell, that distance is its distance to the closest source.

`js function multiSourceBFS(grid, sources) { const dist = grid.map(row => row.map(() => Infinity)); const q = []; for (const [r, c] of sources) { dist[r][c] = 0; q.push([r, c]); } let head = 0; while (head < q.length) { const [r, c] = q[head++]; for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) { const nr = r + dr, nc = c + dc; if (nr < 0

nc < 0

nr >= grid.length

nc >= grid[0].length) continue; if (dist[nr][nc] !== Infinity) continue; dist[nr][nc] = dist[r][c] + 1; q.push([nr, nc]); } } return dist; } `

This pattern is Rotting Oranges, Walls and Gates, 01 Matrix, and "minimum hops from any of these stations" all at once.

Advanced: 0-1 BFS, Bidirectional BFS, and Friends

0-1 BFS (edges weighted 0 or 1): use a deque. Push to the front when the edge weight is 0, push to the back when it's 1. Same O(V+E) as BFS, but handles weighted graphs where weights are only 0/1. Common in grid problems where moving in your facing direction is free and turning costs 1.

Bidirectional BFS: run BFS from source AND from target simultaneously, alternating which frontier you expand. When the two frontiers meet, you have the shortest path. Slashes the explored space from O(b^d) to O(2 · b^(d/2)) — a huge win on word-ladder-style problems with large branching factors.

A*: BFS / Dijkstra ordered by \g(n) + h(n)\ where \h\ is an admissible (under-estimating) heuristic. Same correctness as Dijkstra, dramatically faster when goal-directed.

Advanced: DFS Edge Classification and What It Buys You

During a DFS on a directed graph, every edge is one of:

Type	Description	Signals
Tree edge	edge in the DFS tree	discovery
Back edge	points to a GRAY ancestor	cycle
Forward edge	points to a BLACK descendant	already explored from u
Cross edge	points to a finished node not in u's ancestry	already explored elsewhere

Undirected graphs only have *tree* and *back* edges. This classification is the foundation of Tarjan's bridges and articulation points and Tarjan's SCC — they all depend on knowing which edges close back to ancestors.

Practice Path

1. Write \bfs(adj, start)\ returning the shortest-distance map. Test it on a small graph and confirm the distance to each vertex equals the minimum number of edges from start. 2. Count connected components in an undirected graph by looping over all vertices and launching DFS from each unvisited one. Verify on a forest of 3 trees. 3. Implement bipartite check with BFS 2-coloring. Test on a 4-cycle (true) and a 5-cycle (false). 4. Write Kahn's topological sort and use it to solve "Course Schedule" — return whether all N courses can be finished given prerequisite pairs.