DFS idea

Follow a branch to the end before backtracking.

DFS idea

Depth-first search (DFS) follows a branch to the end, then backtracks at dead ends.

So DFS is naturally implemented with recursion or a stack; depth first is the priority.

DFS is often used for cycle detection, topological sort and pathfinding; its complexity is O(V + E).

Backtracking

Returning from a dead end to try another branch is called backtracking. This is core to DFS.

The state of returning branches is preserved; the path completes and no branch is skipped.

Thanks to backtracking, DFS safely visits every vertex even on cyclic graphs.

Exercise DFS order

Write dfs_order(graph, start). Run stack-based DFS and return the visit order. Print [0, 2, 3, 1] with print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)).

Show example solution

def dfs_order(graph, start):
    # Stack-based DFS
    visited = []
    stack = [start]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.append(node)
            for nb in reversed(graph[node]):
                if nb not in visited:
                    stack.append(nb)
    return visited
print(dfs_order({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0))

Test yourself

Which structure naturally implements DFS?
- Stack or recursion
- Only a queue
- Only a heap
- Hash table
Show answer

Stack or recursion — Stack or recursion.
DFS start
```
stack = [____]
```
Show answer
```
stack = [start]
```
DFS idea: match the terms

DFS

Deep
stack

LIFO
BFS

Layer
recursion

Self-call

Next lesson: Stack or recursion

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies