1. Concept library
  2. Data Structures & Algorithms
  3. Module 11: Graphs

Concept

Depth-first search

DFS follows one path as far as it goes before backing up, using recursion or an explicit stack. It finds connected components, detects cycles, and underlies topological sort and backtracking.

What a session covers

The tutor works through these with you, in conversation and code. A session ends when you have shown them, not when a video does.

  1. Explain how DFS explores and backs up
  2. Write DFS both recursively and with an explicit stack
  3. Use DFS to count connected components or detect a cycle

In practice

A few lines that show Depth-first search doing its job.

Python
def count_components(graph, nodes):
    seen = set()

    def dfs(node):
        stack = [node]
        while stack:
            n = stack.pop()
            if n in seen: continue
            seen.add(n)
            stack.extend(graph[n])

    count = 0
    for node in nodes:
        if node not in seen:
            dfs(node); count += 1
    return count

The common mistake

Watch for

Recursing on a large graph or grid and hitting the recursion limit. Python's default limit is 1000 frames, so a 100 by 100 grid can crash a recursive DFS. Use an explicit stack.

What to know first

Your roadmap puts these before Depth-first search, unless you already know them.

How it stays learned

Once a session shows you understand Depth-first search, it comes back for review. Each review takes a minute and tells the memory model how well you still know it.

  1. Day 3First recall, while it is fresh
  2. Day 7Second, a week on
  3. Day 18Last, when it has settled

Where it leads

Topics that build on Depth-first search.

Previous in the module← Breadth-first search