How Depth-First Search Works

Depth-first search walks as far as it can down one path before backtracking, using a stack — or the call stack. The same loop as BFS with a different container, and a completely different traversal.

On the stack

Visit order

Not reached
Waiting
Current
Finished

Speed

Step 1 of 20

Start at A. Depth-first follows one branch as far as it goes.

Counters

Visited: 1/8
On the stack: 1
Nodes: 8
Edges: 10

Settings

Graph

Start fromA

Depth-first

1stack = [start]
2while stack:
3 node = stack.top
4 if node has an unseen neighbour:
5 mark it seen
6 stack.push(it)
7 else:
8 stack.pop() // done here

What each one answers

Algorithm	What it answers	Time	Needs
Breadth-first	Fewest hops from the start	O(V + E)	A queue
Depth-first	Reachability, one branch at a time	O(V + E)	A stack
Cycle detection	Does a cycle exist, and where	O(V + E)	Node colours
Topological sort	A valid order to do the work in	O(V + E)	No cycles
Dijkstra	Cheapest path by edge weight	O(E log V)	Non-negative weights

V is the number of nodes and E the number of edges. Switch to the graph with a cycle and the topological sort gets stuck: once a cycle exists there is no valid order.

Complexity

Best	Average	Worst	Extra memory
O(V + E)	O(V + E)	O(V + E)	O(V)

Same bound as BFS. Recursion depth can reach V, so a long path in a large graph will overflow a call stack that an explicit stack would survive.

How depth-first search works

Depth-first search picks a neighbour and commits to it, going deeper until it reaches a vertex with nothing new to visit, then backtracks to the most recent vertex that still has unexplored neighbours. Swap BFS's queue for a stack and you have it — which is why the two are usually written as the same loop. The order it finishes vertices in, rather than the order it discovers them, is what makes it the basis for topological sorting and cycle detection.

Mark the start visited.
Pick an unvisited neighbour and descend into it, repeating this rule.
When a vertex has no unvisited neighbours, it is finished — back up to its predecessor.
Continue until every vertex reachable from the start is finished.

Implementation

The same algorithm the visualiser is running, written to be read.

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for neighbour in graph[node]:
        if neighbour not in visited:
            dfs(graph, neighbour, visited)
    return visited


def dfs_iterative(graph, start):
    """BFS's loop with a stack instead of a queue - that is the only change."""
    visited, stack = set(), [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in visited:
                stack.append(neighbour)
    return visited

When to use it

Use it to detect cycles, to find strongly connected components, and to topologically sort — all of which depend on the order vertices finish in.
Use it when the graph is deep and you just need to reach something rather than reach it quickly, or when memory is tight: DFS holds one path, BFS holds one level.
Use the iterative form for large graphs; recursion depth is the practical limit on the recursive one.
Avoid it for shortest paths. The first path DFS finds is often the longest one.

Check yourself

If the animation made sense, these should too.

Why is DFS the basis for cycle detection and topological sort, when BFS is not?

Because those problems depend on the order vertices *finish* in, not the order they are discovered. DFS's recursion gives a finish time per vertex for free; BFS has no equivalent notion.

When is the iterative version not just a style preference?

When the graph is deep. Recursion depth can reach the number of vertices, and a long path in a large graph overflows the call stack - a crash an explicit stack on the heap simply does not have.