DFS

Worked by hand

Trace by hand

Same graph, neighbours tried in the listed order. The stack shows the recursion depth.

step	at	action	stack (top at right)
1	A	enter A, go to B	A
2	B	enter B; A is seen, go to D	A B
3	D	enter D; dead end, return	A B D
4	B	back in B, go to E	A B
5	E	enter E; B is seen, go to F	A B E
6	F	enter F; E seen, go to C	A B E F
7	C	enter C; all seen, return through F, E, B, A	A B E F C

1
Visit order: A, B, D, E, F, C
Unlike BFS (A, B, C, D, E, F) C is last, because the search went A to B to E to F to C before coming back to A's second neighbour.
2
Why not shortest paths
DFS reached C through a long route (4 edges from A). A directly adjacent C was visited last. So DFS distances are not shortest.

Implementation

Recursive DFS

The code mirrors the idea: mark, record, then recurse into each unseen neighbour.

Plan in plain steps

pseudocode

visit(u):
    mark u seen, record u
    for each neighbour v of u:
        if v not seen: visit(v)

python

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def dfs_order(graph, start):
    seen, order = set(), []
    def go(u):
        seen.add(u)
        order.append(u)
        for v in graph[u]:
            if v not in seen:
                go(v)
    go(start)
    return order

print(dfs_order(graph, "A"))   # ['A', 'B', 'D', 'E', 'F', 'C']

Reading the code

›go is defined inside so it can use seen and order without passing them around.
›We check v not in seen *before* the call, which keeps the call stack from growing for nodes already visited.
›Python limits recursion depth to about 1000 by default. On a path-like graph with 10^5 nodes, raise it (sys.setrecursionlimit) or use the iterative version below.

Implementation

Iterative DFS with an explicit stack

Replace the call stack with your own list used as a stack. It avoids the recursion limit and is often a touch faster.

python

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}

def dfs_iterative(graph, start):
    seen, order, stack = set(), [], [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(graph[u]):
            if v not in seen:
                stack.append(v)
    return order

print(dfs_iterative(graph, "A"))   # ['A', 'B', 'D', 'E', 'F', 'C']

Reading the code

›A list with append and pop is a stack (last in, first out).
›We mark a node when it is popped, not when pushed, and skip it if already seen, because the same node can be pushed several times before it is popped.
›reversed(...) pushes neighbours in reverse so the first neighbour ends on top and is visited first, matching the recursive order. The order does not affect correctness, only which valid DFS order you get.

Implementation

Counting connected components

A connected component is a group of nodes that can all reach each other. Start a DFS from every node that is still unseen; each start is one new component.

python

def components(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    seen = [False] * n
    count = 0
    for s in range(n):
        if not seen[s]:
            count += 1
            seen[s] = True
            stack = [s]
            while stack:
                u = stack.pop()
                for v in g[u]:
                    if not seen[v]:
                        seen[v] = True
                        stack.append(v)
    return count

print(components(6, [(0, 1), (1, 2), (3, 4)]))   # 3

Reading the code

›Nodes 0, 1, 2 form one component, 3 and 4 another, and 5 is alone: three in total.
›Here we mark on push (like BFS), which is also valid and avoids duplicate pushes. Both styles work; be consistent within one function.
›Total work is O(V + E): the outer loop visits each node once, and each edge is scanned from both ends.

Worked problem

Count the islands

The problem

A grid contains "1" (land) and "0" (water). An island is a group of land cells connected up, down, left or right. Count the islands.

Scan every cell. When you find land that has not been seen, that is a new island: add 1.
Immediately flood it: DFS through all connected land and mark each cell seen, so the same island is never counted twice.
Continue scanning.

python

def count_islands(grid):
    R, C = len(grid), len(grid[0])
    seen = set()
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1" and (r, c) not in seen:
                count += 1
                seen.add((r, c))
                stack = [(r, c)]
                while stack:
                    x, y = stack.pop()
                    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < R and 0 <= ny < C and grid[nx][ny] == "1" and (nx, ny) not in seen:
                            seen.add((nx, ny))
                            stack.append((nx, ny))
    return count

print(count_islands(["11000", "11000", "00100", "00011"]))   # 3

Takeaway. “Count the groups” is DFS (or BFS) started once per unseen member. The seen set makes each cell cost O(1), so the whole scan is O(R × C).

Worked problem

Detect a cycle in an undirected graph

The problem

Given n nodes and a list of undirected edges, return True if the graph contains a cycle.

Run DFS and carry the node we came from (the parent).
If we meet an already-seen neighbour that is not the parent, we have found a second route to it: that is a cycle.
The edge back to the parent is just the edge we arrived by, so ignore it.

python

def has_cycle(n, edges):
    g = [[] for _ in range(n)]
    for a, b in edges:
        g[a].append(b)
        g[b].append(a)
    seen = [False] * n
    def go(u, parent):
        seen[u] = True
        for v in g[u]:
            if not seen[v]:
                if go(v, u):
                    return True
            elif v != parent:
                return True
        return False
    return any(not seen[s] and go(s, -1) for s in range(n))

print(has_cycle(4, [(0, 1), (1, 2), (2, 0)]))   # True
print(has_cycle(4, [(0, 1), (1, 2), (2, 3)]))   # False

Takeaway. A tree has exactly V − 1 edges and no cycle; a DFS that meets a seen non-parent neighbour has proven a cycle. (Repeated parallel edges need extra care.)

Wrap-up

Remember this

DFS dives as deep as possible before backing up; the call stack (or your own stack) remembers where to return.
A seen set makes it terminate on cycles and keeps the cost at O(V + E).
Use it for connectivity, counting components, flood fill and cycle detection, not for shortest paths.
Use an explicit stack when recursion might go too deep.
In undirected cycle detection, ignore the edge back to the parent.

Cheat sheet

Recursive: mark u; for v in adj[u]: if not seen: go(v)
Iterative: stack; pop; skip if seen; mark; push unseen neighbours
Cost: O(V + E); grid O(R × C)
Good for: connectivity, components, cycles, flood fill, ordering
Not for: shortest paths (use BFS / Dijkstra)
Watch: recursion depth; mark seen before diving

Top traps to avoid

Forgetting the seen set.
Expecting DFS to give shortest paths.
Hitting Python's recursion limit on large inputs.

Mastery check

0 of 15 answered

Answer from understanding, not memory of the page. You need 12 of 15. Each answer is explained, and you can retry as often as you like.

1.What is the main difference between DFS and BFS in terms of data structure?
2.On the lesson graph, with neighbours tried in listed order, what is the DFS visit order from A?
3.Which problem is better solved with BFS than DFS?
4.What is DFS's time on a graph with V nodes and E edges (adjacency lists)?
5.In undirected cycle detection, why do we pass the parent?
6.What can go wrong with recursive DFS on a graph that is one long chain of 100,000 nodes in Python?
7.Graph {1:[2,3], 2:[4], 3:[], 4:[]}. What is the DFS preorder from node 1?
8.Nodes 1 to 5 with edges (1,2) and (3,4). How many connected components are there?
9.What data structure does an iterative DFS use in place of the call stack?
10.Running time of DFS on n nodes and m edges?
11.Directed graph 1->2->3->1. Using DFS with three colours (unseen, in progress, finished), is there a cycle?
12.What is the main difference in the order DFS and BFS visit nodes?
13.Tree: 1 with children 2 and 3; node 2 has child 4. What is the depth, counted in nodes on the longest root-to-leaf path?
14.Why can recursive DFS fail on very large inputs?
15.Post-order DFS (append a node after its children) on 1->2 and 1->3. What is the order?

After this lesson you will be able to

Builds on

Unlocks

Exploring a cave with a ball of string

Depth first versus breadth first

Without a seen set

Mark before you dive, and skip anything marked

DFS on the same six-node graph

Trace by hand

Recursive DFS

Reading the code

Iterative DFS with an explicit stack

Reading the code

Counting connected components

Reading the code

Why O(V + E)

Edge cases

Mistakes to avoid

How to spot a DFS problem

Count the islands

Detect a cycle in an undirected graph

Wrap-up

Remember this

Cheat sheet

Top traps to avoid

Mastery check

Practice this topic

Warm-up3 problems

Core7 problems

Application21 problems

Challenge22 problems