Breadth-first search: the idea
Prerequisites: Nodes, edges, and a first-in-first-out queue.
A graph consists of nodes and the edges connecting them. Breadth-first search maintains a queue: the first node added is the first removed. When a node is removed, its undiscovered neighbors join the back of the queue. This visits nodes in increasing distance measured in edges. Recording the node that discovered each neighbor lets us reconstruct a path.
Try it on the same input
Start at A and aim for I on the “Weighted routes” map. Breadth-first search finds a path with four edges: A → B → D → G → I, with total weight 25. Dijkstra and A* find A → C → E → H → I, also four edges but with total weight 9. Now add an A–I connection with weight 99. Breadth-first search takes that one-edge route; Dijkstra and A* keep the cheaper route.
When to use it—and what to watch
Edge weights are ignored. A three-edge route can cost more than a four-edge route. Use this algorithm when each move has equal cost, or when the number of connections is what matters.
Time and memory
V means the number of nodes; E means the number of edges. O(V + E) with adjacency lists. These finite graph searches store visited-node information, predecessors, and a stack or frontier, requiring O(V) search memory.
The executable teaching version deliberately uses arrays: it scans the edge list to find neighbors and, for priority-based searches, sorts the frontier to select a minimum. It therefore does not achieve the adjacency-list or heap bounds quoted above. Recorded playback also stores a snapshot at each operation, using more memory than the search itself. The fixed nine-node graph keeps this small and makes the state easy to inspect.
Reading the display
For frontier-based searches, the frontier contains discovered nodes waiting to be explored. “Previous” records the predecessor used to reach a node. Dashed cyan arrows point back to those predecessors. ∞ means no route to that node has been discovered yet. Pink marks the current node or inspected connection; green marks the completed path. All connections are undirected: you can travel either way.
The Code panel shows explanatory pseudocode. The linked JavaScript is the executable implementation that produces every playback frame. A step can check a condition without changing the table; watch the highlighted line and explanation together.
Continue exploring
- Dijkstra’s algorithm — Explore the cheapest known route first. Minimize total weight.
- A* search — Combine cost so far with an estimate of the journey remaining.
- Depth-first search — Follow one branch deeply, then backtrack when it runs out.
- Bidirectional breadth-first search — Search outward from both endpoints and join where the searches meet.
- Greedy best-first search — Head toward the most promising-looking node, ignoring cost already paid.