Graph Algorithms
Graph BFS (Breadth-First Search)
Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.
1Detailed explanation
Breadth-first search starts at a vertex, visits all of its neighbours, then all vertices two edges away, and so on. A FIFO queue keeps the discovered-but-unprocessed vertices in exactly that order.
A vertex is marked visited when it is discovered (enqueued), not when it is processed, so it can never be enqueued twice.
Because vertices are discovered in order of distance, dist[v] = dist[parent] + 1 gives the shortest number of edges from the start — BFS is the shortest-path algorithm for unweighted graphs.
2Pseudocode
procedure BFS(G, start)
visited ← {start}
dist[start] ← 0
queue ← [start]
while queue not empty
u ← dequeue(queue)
visit u
for each neighbor v of u
if v ∉ visited
visited ← visited ∪ {v}
dist[v] ← dist[u] + 1
enqueue(queue, v)3Interactive visualization
Queue (front → rear)
Traversal order
Explores the graph level by level using a queue. Because vertices are discovered in order of distance, BFS also finds the shortest path (fewest edges) from the start in an unweighted graph.
4Implementations
Equivalent implementations in four languages — the same code the visualizer highlights line by line. Each is a complete program.
function bfs(graph, start) {
const visited = new Set([start]);
const dist = { [start]: 0 };
const queue = [start];
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
dist[neighbor] = dist[node] + 1;
queue.push(neighbor);
}
}
}
return { order, dist };
}
const edges = [["A", "B"], ["A", "C"], ["B", "D"], ["B", "E"], ["C", "F"], ["E", "F"], ["D", "G"], ["F", "G"]];
const graph = {};
for (const [u, v] of edges) {
(graph[u] ??= []).push(v);
(graph[v] ??= []).push(u);
}
const { order, dist } = bfs(graph, "A");
console.log("BFS order:", order.join(" -> "));
console.log("Distances:", order.map((v) => v + "=" + dist[v]).join(", "));
5Time and space complexity
Time: Every reachable vertex is enqueued and dequeued once (O(V)) and every adjacency list is scanned once; in an undirected graph each edge appears twice → O(E). Total O(V + E).
Space: visited, dist and the queue each hold at most V vertices → O(V) auxiliary space. The adjacency list input itself takes O(V + E).
6Common interview variations
- Shortest path in an unweighted graph / grid.
- Number of islands (BFS on a grid).
- Level order traversal of a tree.
- Word ladder.
- Check whether a graph is bipartite.