Set your Publisher ID in src/config/ads.ts to display live ads.
Graph Traversals: BFS, DFS & Shortest Paths
Adjacency lists, visited sets, Breadth-First vs Depth-First, and Dijkstra
Graphs model networks of entities (vertices/nodes) connected by relationships (edges). Traversing graphs requires tracking visited nodes to avoid infinite cycles.
BFS vs DFS in Graphs
Adjacency List: The standard memory-efficient graph representation: a map where each node points to an array of its neighbors.
Breadth-First Search (BFS): Explores concentric ripples using a Queue. Guarantees finding the shortest path on unweighted graphs.
Depth-First Search (DFS): Explores as deeply as possible along each branch using recursion or a Stack. Ideal for cycle detection and maze solving.
Dijkstra's Algorithm: Finds the shortest path in weighted graphs with non-negative edge weights using a priority queue (min-heap).
function bfsShortestPath(graph, start, target) {
const queue = [[start, 0]]; // [current_node, distance]
const visited = new Set([start]);
while (queue.length > 0) {
const [node, dist] = queue.shift();
if (node === target) return dist;
for (const neighbor of graph[node] || []) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, dist + 1]);
}
}
}
return -1; // Unreachable
}
const network = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B', 'F'],
'E': ['C'],
'F': ['D']
};
console.log("Shortest hops A -> F:", bfsShortestPath(network, 'A', 'F')); // 3 hopsSet your Publisher ID in src/config/ads.ts to display live ads.
Test Yourself With Exercise
Which graph traversal algorithm guarantees finding the shortest path on an unweighted graph?