Depth-First Search (DFS) Calculator

Read the Theory Guide →

Build an unweighted graph, choose a start and a goal, and run DFS to see the LIFO stack and visited nodes at every step. Edit the graph or its direction and rerun to see how the search order changes.

What You Can Explore

  • Build a graph on the canvas, or edit the preloaded one by adding, moving, and connecting nodes.
  • Switch between directed and undirected graphs to change which connections DFS can follow.
  • Choose the Starting Point and Goal Point, then press Run DFS to search the graph.
  • Step through the resolution to follow the LIFO stack, the node being evaluated, and the Closed List at each step.
Core Mechanics
▼
  • The LIFO Stack: DFS strictly runs on "Last-In, First-Out". You always push newly discovered neighbors to the *top* of the stack, and immediately pop the next evaluating node from that exact same spot.
  • Deep Dives & Backtracking: By always picking the newest node, DFS plunges as deep as mathematically possible down a single path. It only "backtracks" to explore alternative routes when it hits an absolute dead end.
  • First, Not Fastest (Not Optimal): DFS does *not* care about finding the shortest path. It blindly returns the very first valid route to the goal it stumbles upon, completely ignoring edge costs and hop counts.
  • The Infinite Loop Trap: Without a strict Closed List (Visited set), DFS will run in circles forever on cyclic graphs. Once a node is evaluated, lock it away and ignore it forever!
Initializing Workspace...

Understanding Your Result

The path and trace come from your graph and the selected start and goal. The summary shows the first path DFS finds and its length in edges, while the stack trace shows the order in which nodes were explored.

  • Total Path Steps counts the edges in the path DFS returned. DFS finds a path, but it does not guarantee the path with the fewest edges.
  • The Evaluating Node is the node at the top of the LIFO stack. Newly added nodes are explored before nodes that have been waiting longer.
  • The Closed List records nodes that have already been evaluated. It can contain nodes that are not part of the final path because DFS may explore and abandon a branch.
  • DFS explores one branch as deeply as possible before backtracking. When no route exists, the search continues until all reachable nodes have been explored.

Try These Experiments

Connect E to G

Setup: Run the preloaded graph with S as the start and G as the goal, and note the path and Total Path Steps.

Action: Draw a new edge from E to G, keep the same start and goal, and run DFS again.

What to Observe: Compare the path and Total Path Steps with the first run. Then check the final Closed List to see whether B was evaluated.

Takeaway: DFS follows the current branch as deeply as possible before backtracking. With E connected directly to G, DFS reaches the goal through the left branch before it needs to explore B, even though the original path through B is shorter.

Choose a Shallow Goal

Setup: Keep the preloaded graph and change the Goal Point from G to B, which is one edge away from S.

Action: Run DFS and inspect the Closed List at the final step. Then compare it with the one-edge path shown in the summary.

What to Observe: The returned path is only one edge long, but the Closed List shows that DFS explored the entire left branch before reaching B.

Takeaway: Being close to the start does not mean DFS will reach a goal quickly. DFS follows its stack order and can explore a deeper branch before returning to a node that leads directly to the goal.

Add a Cycle

Setup: Run the preloaded graph once and note the returned path and the nodes shown in the Closed List.

Action: Draw an edge from E back to A, creating a cycle, then run DFS again with the same start and goal.

What to Observe: Compare the path and the search trace with the first run. Check whether A is added to the Open List a second time.

Takeaway: Visited nodes are not queued again, so the new cycle does not make DFS loop forever. Once A has already been visited, the edge from E back to A does not cause A to be explored again.