HomeConceptsComputer ScienceAlgorithms and Search

Computer Science · Algorithms and Search

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

DFS expands the newest waiting node first because the frontier behaves like a stack.
The current depth can rise quickly because DFS stays with one branch until it cannot continue.
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.

See how a stack frontier turns local neighbors into one deep branch

Keep this idea moving

Open the next concept, route, or track only when you want the current model to widen into a larger branch.

See why branch-first search still needs clean cycle bookkeepingAlgorithms and Search

Frontier and Visited State on Graphs

Use one cyclic graph to see which nodes are waiting, which are finished, and why repeat edges are skipped instead of reopening loops.

Return to the queue-based contrast on the same graphAlgorithms and Search

Breadth-First Search and Layered Frontiers

Keep the queue frontier, visited count, and graph layers visible together so breadth-first search reads as a layered process instead of a procedure list.

Next in Graph neighborhoods and adjacencyAlgorithms and Search

Graph Representation and Adjacency Intuition

Keep one live graph, one local neighborhood, and one frontier cue visible together so graph structure feels readable before traversal rules get formal.

Stay with this concept

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

More practice optionsReview on the bench · Worked examples

Practice optionReview on the benchReplay the guided setup with the key controls and graphs in sight.
Practice optionWorked examplesCompare against solved walkthroughs after you try the setup yourself.
Practice optionFree play on the benchExperiment freely with the live controls before moving to another concept.

Reference and support

Use these calmer sections when you want a fuller explanation, examples, or accessibility support after the guided flow.

Return here when you want the slower reference pass.

Open reference and support

Equation snapshotBranch depth rule · Stack frontier updateShow 2 equations

Branch depth rule
$d (u) = d (v) + 1$
A newly discovered neighbor is one edge deeper than the node that found it.
Stack frontier update
$S_{n e x t} = S ∖ {v_{t o p}} \cup N_{n e w} (v_{t o p})$
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

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?

G

Graph layout

Layered campus

s

Start node

S

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.

Starter track

Step 5 of 6

Algorithms and Search Foundations

Depth-First Search and Backtracking Paths appears later in this track, so it is cleaner to start from the beginning first.

Previous step: Breadth-First Search and Layered Frontiers

Start from track beginning