Summary - DFS

Run DFS on a graph and print the order in a mini task.

Summary - DFS

DFS dives deep with a stack or recursion and backtracks at dead ends. It is used for pathfinding, cycle detection and topological sort.

In this mini task you will run DFS and print the visit order; combine all steps.

DFS walks deep graphs efficiently; this is why it is preferred for connectivity analysis and sorting.

Exercise Print DFS

Write dfs_print(graph, start). Run stack-based DFS and print the visit order with print(). Output: [0, 2, 3, 1].

Show example solution

def dfs_print(graph, start):
    # Print DFS order
    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)
    print(visited)
dfs_print({0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}, 0)

Test yourself

Summary - DFS: match the terms

DFS

Stack
recursion

Self-call
backtrack

Return
visited

No repeat
Stack op
```
node = stack.____
```
Show answer
```
node = stack.pop()
```
What is DFS's time complexity?
- O(V log V)
- O(V + E)
- O(E^2)
- O(V!)
Show answer

O(V + E) — O(V + E).

Next lesson: Greedy approach

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies