Graph Traversals: BFS & DFS for Connected Components
Quick Overview
BFS and DFS visit the same vertices and differ only in order. On an unweighted graph BFS reaches each node by fewest edges (why it finds shortest paths and DFS cannot), both in `O(V + E)`.
Deep Dive
1. Navigating Cyclic Networks
Unlike trees, graphs can contain cycles (loops). To prevent infinite recursion or infinite loops, every graph traversal algorithm MUST maintain a visited set of explored vertices.
2. Graph Depth-First Search (DFS)
DFS explores as far along a path as possible before backtracking:
function dfsGraph(startNode, adjList) {
const visited = new Set();
const traversalOrder = [];
function explore(node) {
visited.add(node);
traversalOrder.push(node);
for (const neighbor of adjList.get(node) || []) {
if (!visited.has(neighbor)) {
explore(neighbor); // Recurse on unvisited neighbor
}
}
}
explore(startNode);
return traversalOrder;
}
3. Graph Breadth-First Search (BFS) & Shortest Path
BFS explores concentric rings of neighbors, guaranteeing the shortest path in unweighted graphs:
function shortestPathUnweighted(start, target, adjList) {
const visited = new Set([start]);
const queue = [[start, 0]]; // [currentNode, distance]
while (queue.length > 0) {
const [current, dist] = queue.shift();
if (current === target) return dist; // Shortest distance found!
for (const neighbor of adjList.get(current) || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
return -1; // Unreachable
}
4. Number of Connected Components (Islands)
To count isolated components, iterate over all vertices and trigger DFS for each unvisited node:
function countComponents(numNodes, adjList) {
const visited = new Set();
let count = 0;
for (let i = 0; i < numNodes; i++) {
if (!visited.has(i)) {
count++;
// Trigger DFS to mark all connected vertices as visited
dfsGraph(i, adjList);
}
}
return count;
}
5. Common Mistakes
- Forgetting Visited Set in BFS: Pushing neighbors to the queue without marking them in
visitedimmediately causes duplicate queue entries, leading to exponential memory exhaustion!
6. Next Steps
Use BFS for unweighted shortest paths. Next, let's enter Phase 4 and master Topological Sort on DAGs!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.