Skip to content
Open Model LabInteractive concept
HomeConcept libraryComputer ScienceAlgorithms and SearchAlgorithms and Search Foundations
Computer ScienceAlgorithms and SearchIntroStarter track

Concept module

Depth-First Search and Backtracking Paths

Keep the stack frontier, current depth, and branch order visible together so depth-first search feels like disciplined backtracking instead of random wandering.

Interactive lab

Loading the live simulation bench.

Progress

Not startedMastery: NewLocal-first

Start exploring and Open Model Lab will keep this concept's progress on this browser first. No finished quick test, solved challenge, or completion mark is saved yet.

Let the live model runChange one real controlOpen What to notice

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.

Featured setups

Layered campus DFS

Use the same graph as BFS, but let the newest branch stay on top.

Bridge cycle DFS

Watch depth-first search dive into one side of a looped graph before it backtracks.

Saved setups

Premium keeps named exact-state study setups in your account while stable concept links stay public below.

Checking saved setup access.

This concept can keep using stable links while the saved-setups capability resolves for this browser.

Copy current setup

Stable concept and section links stay public below while exact-state setup sharing stays behind premium.

Stable links

Starter track

Step 5 of 60 / 6 complete

Algorithms and Search Foundations

Earlier steps still set up Depth-First Search and Backtracking Paths.

1. Sorting and Algorithmic Trade-offs2. Binary Search / Halving the Search Space3. Graph Representation and Adjacency Intuition4. Breadth-First Search and Layered Frontiers+2 more steps

Previous step: Breadth-First Search and Layered Frontiers.

Start from track beginning

Why it behaves this way

Explanation

Depth-first search keeps the frontier organized like a stack. The newest claimed node is the next one to expand, so the search dives down one branch as far as it can before it has to return.

That stack behavior is easiest to trust when the graph, the frontier chips, and the depth graph all stay visible. The bench shows that DFS is not random wandering. It is a disciplined branch-first rule on the same graph that BFS uses.

Key ideas

01Depth-first search expands the newest waiting node first.
02DFS often raises the current depth quickly because it stays with one branch until it cannot continue.
03Backtracking happens when the top branch is exhausted and the frontier falls back to an older waiting node.

Frozen walkthrough

Step through the frozen example

Frozen walkthrough
Read the stack frontier directly from the layered-campus bench.

Premium 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 changes when DFS starts from A?

Graph layout

Layered campus

Start node

A

Stack frontier

B below C

1. Read the first stack order

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

2. Read the next branch move

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

3. Name the branch-first consequence

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

DFS branch read

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.

Common misconception

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

A deep branch is not the same thing as a short path. DFS can commit to a long detour before it notices a shallower alternative.

The point of DFS is the branch-first frontier rule, not guaranteed shortest routes.

Mini challenge

Build a DFS case where the current depth rises quickly before the target is reached.

Make a prediction before you reveal the next step.

Decide whether you need a layered graph or a hub-like graph before you switch presets.

Check your reasoning against the live bench.

Use a graph with a clear branch so DFS can keep the newest path on top for several steps.
Depth-first search dives fastest when one branch keeps discovering one new neighbor at a time.

Quick test

Reasoning

Question 1 of 2

Answer from the visible stack and branch behavior, not from memorized acronyms.

Why does DFS usually feel deeper before it feels wider on this bench?

Use the live bench to test the result before moving on.

Accessibility

The simulation shows one labeled graph with the current node, the stack frontier, and the visited nodes colored differently so the active branch stays readable.

A readout card reports the traversal mode, current node, frontier size, visited count, and target, while a cue panel shows the frontier order and the current neighbor list.

Graph summary

One graph tracks visited nodes against frontier size, a second tracks current depth against the deepest claimed depth, and a third compares new discoveries with repeat skips.

Together they show how depth-first search dives into a branch and then backtracks when that branch runs out.