Graph Algorithms

How Depth-First Search Works

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

ABCDEFGH
On the stack
  1. A
Visit order
  1. A
  • Not reached
  • Waiting
  • Current
  • Finished
1/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
More options

Depth-first

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

What each one answers

AlgorithmWhat it answersTimeNeeds
Breadth-firstFewest hops from the startO(V + E)A queue
Depth-firstReachability, one branch at a timeO(V + E)A stack
Cycle detectionDoes a cycle exist, and whereO(V + E)Node colours
Topological sortA valid order to do the work inO(V + E)No cycles
DijkstraCheapest path by edge weightO(E log V)Non-negative weights

Scroll the table sideways for the rest of the columns.

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

BestAverageWorstExtra 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 basically have it; the two are usually written as one loop with the container swapped. The part that matters later is the finish order, not the discovery order. Topological sort and cycle detection are both built on it.

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

Implementation

Python
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 three 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.

More graph algorithms