Skip to content
Open Model Lab

Depth-First Search and Backtracking Paths

Simulation loading

Open Model Lab is preparing the live lab, controls, and graph surface for this concept.

Wrap-up

What you learned

Recommended next
Open concept testCheck whether the core ideas are ready without leaving this concept.
Read next
Frontier and Visited State on GraphsSee why branch-first search still needs clean cycle bookkeeping

Key takeaway

  1. DFS expands the newest waiting node first because the frontier behaves like a stack.
  2. The current depth can rise quickly because DFS stays with one branch until it cannot continue.
  3. Backtracking happens naturally when the top branch runs out and the stack exposes an older unfinished node.

Common misconception

Depth-first search reaches the target fastest because it goes straight down one branch.

Going deeper first is not the same as finding a short route. DFS can spend time on a long detour before it reaches an easier target on another branch.

Stay with this concept

Review, test, or free-play here when you want one more same-concept pass.

  1. Recommended nextOpen concept testCheck whether the core ideas are ready without leaving this concept.
  2. Practice optionChallenge modeChallenge mode stays available as a secondary path after the core lesson flow.
  1. Practice optionReview on the benchReplay the guided setup with the key controls and graphs in sight.
  2. Practice optionWorked examplesCompare against solved walkthroughs after you try the setup yourself.
  3. Practice optionFree play on the benchExperiment freely with the live controls before moving to another concept.

Read next

Keep the sequence moving with the most relevant follow-up concept.

  1. Read nextSee why branch-first search still needs clean cycle bookkeepingFrontier and Visited State on Graphs
    1. Read nextReturn to the queue-based contrast on the same graphBreadth-First Search and Layered Frontiers

  1. Branch depth rule

    A newly discovered neighbor is one edge deeper than the node that found it.

  2. Stack frontier update

    DFS removes the newest frontier node first, then places newly discovered neighbors on top of the stack.

Why it behaves this way

Explanation

Depth-first search keeps its frontier in stack order. The newest discovered node is expanded next, so the search usually follows one branch as far as it can before returning.

On this bench, keep the graph, frontier cue, and depth history visible together. That makes DFS easier to read: it is not random wandering, and it is not a shortest-path method. It is a branch-first rule applied step by step to the same graph that BFS explores layer by layer.

Key ideas

01Depth-first search expands the newest waiting node first.
02DFS often increases the current depth quickly because it keeps following the active branch.
03Backtracking begins when the current branch has no new neighbors, so the search returns to an older waiting node.

Worked examples

Worked examples

Open examples when you want to see the same idea walked through step by step.

Frozen walkthrough

Step through the frozen example

Frozen walkthrough
Use the frontier order and depth view together to read what DFS does immediately after the start.

Supporter unlocks saved study tools, exact-state sharing, and the richer review surfaces that support this guided flow.

View plans
Frozen valuesUsing frozen parameters

On the layered campus graph, what does DFS do after A discovers both B and C?

Graph layout

Layered campus

Start node

A

Traversal mode

B below C

1. Read which node is on top of the stack

After A claims B and C, both nodes sit on the frontier, but the newest claim C is now on top.

2. Predict the next branch move

Because DFS uses a stack frontier, C leaves next even though B was discovered first.

3. Connect that move to later backtracking

DFS keeps following that newest branch until it runs out of new neighbors, then it backtracks to older waiting nodes like B.

Next DFS move

From A, DFS puts C on top of the stack frontier and dives there next.
The stack frontier is what makes DFS feel deep and path-like on the same graph that BFS explores layer by layer.

Quick test

Loading saved test state.

Bench tools and share links

Keep stable concept links and exact-state sharing tucked away until you actually need to relaunch or share the bench.

Try this setup

Jump to a named bench state or copy the one you are looking at now. Shared links reopen the same controls, graph, overlays, and compare context.

Current bench

Layered campus DFS preset

This bench is currently showing one of the concept's authored presets.

Open default bench

Featured setups

Layered campus DFS

Use the same graph as BFS, then watch DFS follow the newest branch instead of finishing the whole shallow layer first.

Bridge cycle DFS

Watch DFS go deep into one side of a cyclic graph, then backtrack when that branch runs out of new nodes.

Saved setups

Saved setups are a Supporter study tool. Stable concept links still work for everyone.

Checking saved setup access

Open Model Lab is resolving whether this bench can save locally, sync to an account, or open Supporter-only compare tools.

Copy current setup

Exact-state sharing is part of Supporter. Stable concept and section links still stay available.

Stable links

Progress and next steps

Keep progress signals, starter-track handoffs, and review prompts available without letting them compete with the live lesson flow.

Progress

Loading progress

Loading saved concept progress for this browser or synced account before showing completion status.