Depth-First Search: A Complete Solved Numerical Example

Try Depth-First Search Solver →Read Depth-First Search Theory →

Scenario: Software Dependency Resolution

The Objective: A build system must determine if Module G can be reached from the Entry Point (S) by traversing software dependencies. Nodes are expanded alphabetically.

Core Mechanics

▼

The FIFO Queue: BFS strictly runs on "First-In, First-Out". You must pop the oldest node from the front to evaluate it, and push its new neighbors to the back.
Level-by-Level Expansion: It completely finishes exploring depth $d$ before ever touching depth $d+1$ . This guarantees the shortest path based on hop count, ignoring edge costs.
Never Look Back: Once a node enters the Closed List (Visited), ignore it forever. Because BFS expands outward like a ripple, the first time you discover a node is mathematically guaranteed to be the fastest route to it.
The Goal Test (The Final Pop): Even if you see the goal waiting in the Open List, do not stop! You can only declare victory when the goal node is officially popped from the front and becomes the Evaluating Node.

Step 1: Initial Map Configuration

The structure of our network. DFS explores nodes by plunging as deep as possible down a single path before backtracking.

Start Node: SGoal Node: G

Want to edit this data in the live solver?

Step 2: Step-by-Step LIFO Stack Resolution

Step	Open List (Stack)	Evaluating Node	Closed List (Visited)
1	[ S ]	S	[ ]
2	[ B, A ]	A	[ S ]
3	[ B, D, C ]	C	[ S, A ]
4	[ B, D, E ]	E	[ S, A, C ]
5	[ B, D, G ]	G	[ S, A, C, E ]
6	[ B, D ]	Goal Reached	[ S, A, C, E, G ]

Goal Reached

S → A → C → E → G

Total Path Steps: 4

Final Takeaway

Notice how the Last-In, First-Out (LIFO) stack forces the algorithm to tunnel blindly down the left side, locking in the 4-step path (S→A→C→E→G). Because DFS prioritizes depth over efficiency, it completely misses shorter alternatives, proving the ultimate exam rule: DFS never guarantees the shortest route!