Master graph exploration using BFS and DFS with visited tracking sets to detect cycles, count islands, and find shortest paths.
Learn how dynamic arrays achieve O(1) amortized insertion, contiguous memory layout, and geometric doubling strategies.
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!