Depth-first search: the idea
Prerequisites: Nodes, edges, and a last-in-first-out stack.
A stack removes the most recently added item first. This depth-first search stores a frame for each active node: the node and which neighbor to inspect next. It follows one unvisited neighbor immediately. When a frame has no remaining neighbors, it is removed and the search resumes its parent frame. A visited set prevents cycles. The recorded predecessor chain gives a route if the destination is found.
Try it on the same input
Start at A and aim for I on the weighted map. Watch the search descend through B, D, F, E, and C. C is a dead end in the current search tree, so its frame is popped before E resumes and explores H. Open the Code panel to see the backtracking operation. Compare the returned route with breadth-first search; depth-first search follows branch order rather than minimizing edge count.
When to use it—and what to watch
The first route found may have more edges and a larger total weight than another route. Neighbor order matters. This finite graph search remembers visited nodes; an unrestricted depth-first tree search can get stuck following an infinite branch.
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
The stack shows active frames, with the current frame on the left. Ancestors remain on the stack until their neighbors have been inspected. “Tree depth” is the number of edges along the first-discovery route, not a guaranteed shortest distance. “Visited” counts first discoveries.
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
- Breadth-first search — Explore one layer at a time. Find a path with the fewest edges.
- 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.
- 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.