23 of 32 · 6 min

Two ways to walk a graph

Almost every graph question is answered by visiting the vertices in one of two orders. They differ by one line of code and answer different questions.

Breadth first: nearest first

Use a queue. Visit everything one step away, then everything two steps away, and so on.

python

from collections import deque

def bfs(graph, start):
    seen = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                seen.add(neighbour)
                queue.append(neighbour)

Because it expands in rings, the first time it reaches a vertex it has arrived by the fewest edges. So BFS finds the shortest path in an unweighted graph, and that is its main job.

Depth first: as far as possible

Use a stack, or recursion, which is a stack. Follow one path to its end, then back up and try the next.

python

def dfs(graph, node, seen):
    seen.add(node)
    print(node)
    for neighbour in graph[node]:
        if neighbour not in seen:
            dfs(graph, neighbour, seen)

DFS is the tool for questions about structure rather than distance: does a cycle exist, which vertices form a connected group, what is a valid order for these dependencies.

The one line that matters most

python

if neighbour not in seen:

Without the visited set, a graph with a cycle loops forever. This is the single difference between traversing a tree and traversing a graph, and forgetting it is the most common graph bug there is.

	BFS	DFS
Structure	queue	stack or recursion
Finds	shortest unweighted path	any path, and structure
Memory	can be wide	depth of the path
Typical use	shortest hops, level order	cycles, components, topological order

Both are O(V + E): every vertex is visited once and every edge is examined once.

When edges have weights

Neither works. BFS counts edges, so a route of one very long road looks shorter than three short ones. That is Dijkstra's algorithm, which is BFS with a heap instead of a queue, always expanding the nearest unfinished vertex. The heap from the previous page is the whole difference.

Two ways to walk a graph