A girl and a robot thinking together

Think together · Start with a little story

The robot explores a tree house. It follows one branch until there is nowhere new to go, then returns and tries another branch.

Lay out the process

Follow the steps, then explain them in your own words
  1. Start at AChoose B first
  2. From BContinue to D
  3. No new path at DReturn to B
  4. Explore againChoose an unvisited branch

Depth-first search explores one branch deeply before returning to explore others.

A stack or recursion can remember where to return. In a graph with cycles, you also need to manage which states have been visited.

01What is DFS?

DFS (Depth-First Search) follows this basic idea:

Follow one path as deeply as possible; when you cannot go farther, return and choose another

02How do you explore a tree?

A
BC
DEF

Starting at A, you might enter B first, continue deeper into B’s children, and return to A to handle C only after finishing that branch.

03How do you write recursive DFS?

void dfs(int u) {
    visited[u] = true;

    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

Each time you enter a node, recursively visit a neighbor that has not been visited yet.

04Must DFS use recursion?

No. You can also use a stack explicitly:

std::stack<int> st;
st.push(start);

Recursive DFS uses the function-call stack; iterative DFS manages a stack data structure itself.

05Why do graphs usually need visited?

Graphs may contain cycles. If A-B-C-A forms a cycle, failing to record visited states may make the search go around forever.

06What can DFS do?

  • Traverse a graph or tree.
  • Check reachability.
  • Find connected components.
  • Explore choices with backtracking.
  • Provide a foundation for advanced graph algorithms such as topological sorting, bridges, and articulation points.

What have you learned?

  • DFS follows one path as deeply as possible.
  • When it cannot go farther, it returns to the previous level.
  • You can implement DFS with recursion or with a stack.
  • Graphs often need a visited record to prevent repeated visits.
  • DFS is a foundation for many graph and backtracking algorithms.

Next: How Are DFS and Recursion Related?

Your turn to try

If you reach the end of one path without finding the target, should you immediately say it does not exist?

Ready? Open to see the explanation

No. Backtrack to a position with an unexplored branch and continue searching.