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)`.
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.
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;
}
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
}
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;
}
visited immediately causes duplicate queue entries, leading to exponential memory exhaustion!Use BFS for unweighted shortest paths. Next, let's enter Phase 4 and master Topological Sort on DAGs!
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.
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.
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.