Depth First Search

Read that carefully, because it is the point of the chapter. A stack is last in, first out. Pushing A's neighbours in the listed order B then C puts C on top, so C comes off first, and the walk goes down C's branch before B's. The recursion goes down B's branch first, because the for loop reaches B first.

So to make the stack version agree with the recursive one, push the neighbours in reverse. Both are correct depth first searches. They are just different depth first searches, and an exam answer should say which convention it is using rather than assume there is only one order.

What DFS actually does: it goes deep

def adjacency(pairs, vertices):
    graph = {v: [] for v in vertices}
    for a, b in pairs:
        graph[a].append(b)
        graph[b].append(a)
    for v in graph:
        graph[v].sort()
    return graph


EDGES = [("A", "B"), ("A", "C"), ("B", "D"), ("B", "E"),
         ("C", "F"), ("E", "F"), ("E", "G"), ("F", "H")]
GRAPH = adjacency(EDGES, "ABCDEFGH")


def dfs_with_depth(graph, v, visited=None, depth=0, out=None):
    if visited is None:
        visited, out = set(), []
    visited.add(v)
    out.append((v, depth))
    for w in graph[v]:
        if w not in visited:
            dfs_with_depth(graph, w, visited, depth + 1, out)
    return out


print("how far from the start each vertex was when DFS reached it:")
for v, depth in dfs_with_depth(GRAPH, "A"):
    print("   %s%s  (depth %d)" % ("   " * depth, v, depth))
print()
print("compare the BFS levels on the same graph:")
print("   A 0 | B 1 C 1 | D 2 E 2 F 2 | G 3 H 3")
print()
print("DFS reached F at a depth of 3, but F is only 2 edges from A.")
print("DFS depth is NOT the shortest distance. BFS level is.")

how far from the start each vertex was when DFS reached it:
   A  (depth 0)
      B  (depth 1)
         D  (depth 2)
         E  (depth 2)
            F  (depth 3)
               C  (depth 4)
               H  (depth 4)
            G  (depth 3)

compare the BFS levels on the same graph:
   A 0 | B 1 C 1 | D 2 E 2 F 2 | G 3 H 3

DFS reached F at a depth of 3, but F is only 2 edges from A.
DFS depth is NOT the shortest distance. BFS level is.

That is the standard examination trap. A DFS depth is not a distance. DFS found F by going A, B, E, F, so it recorded depth 3, while the shortest route A, C, F is 2 edges. If a question asks for a shortest path in an unweighted graph the answer is BFS, never DFS.

Recursion has a real limit

The recursive version is shorter and clearer, and it has one practical weakness worth knowing: a long path uses one stack frame per vertex, and the call stack is finite.

import sys

sys.setrecursionlimit(1500)          # a modest, explicit limit for this demo


def path_graph(n):
    """0 - 1 - 2 - ... - (n-1). The deepest possible graph."""
    graph = {i: [] for i in range(n)}
    for i in range(n - 1):
        graph[i].append(i + 1)
        graph[i + 1].append(i)
    return graph


def dfs_recursive(graph, v, visited, order):
    visited.add(v)
    order.append(v)
    for w in graph[v]:
        if w not in visited:
            dfs_recursive(graph, w, visited, order)
    return order


def dfs_iterative(graph, start):
    visited, order, stack = set(), [], [start]
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)
        for w in reversed(graph[v]):
            if w not in visited:
                stack.append(w)
    return order


for n in (100, 5000):
    graph = path_graph(n)
    print("a path of %d vertices:" % n)
    try:
        order = dfs_recursive(graph, 0, set(), [])
        print("   recursive : visited all %d" % len(order))
    except RecursionError:
        print("   recursive : RecursionError, the call stack ran out")
    order = dfs_iterative(graph, 0)
    print("   iterative : visited all %d, no error" % len(order))

a path of 100 vertices:
   recursive : visited all 100
   iterative : visited all 100, no error
a path of 5000 vertices:
   recursive : RecursionError, the call stack ran out
   iterative : visited all 5000, no error

The recursive version fails on the long path. The iterative version does not, because its stack is a list on the heap. The limit here was set deliberately so the demonstration is exact rather than dependent on the machine, but the effect is real: on deep graphs the iterative version is the safe one, and that is the honest reason to know both forms.

The cost

Identical to BFS, for the identical reason: every vertex is handled once and every adjacency entry is read once.

def ring_with_chords(n):
    graph = {i: [] for i in range(n)}
    pairs = set()
    for i in range(n):
        for j in ((i + 1) % n, (i * 7 + 3) % n):
            if i != j:
                pairs.add((min(i, j), max(i, j)))
    for a, b in sorted(pairs):
        graph[a].append(b)
        graph[b].append(a)
    return graph, len(pairs)


def dfs_counting(graph, start):
    visited, stack, reads, seen = set(), [start], 0, 0
    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        seen += 1
        for w in graph[v]:
            reads += 1
            if w not in visited:
                stack.append(w)
    return seen, reads


print("%8s %8s %14s %10s %s" % ("vertices", "edges", "entries read", "2E", "equal"))
for n in (10, 100, 1000):
    graph, e = ring_with_chords(n)
    seen, reads = dfs_counting(graph, 0)
    print("%8s %8d %14d %10d %s" % (n, e, reads, 2 * e, reads == 2 * e))
    assert seen == n

print()
print("exactly 2E entries read, the same as BFS: both are O(V + E).")

vertices    edges   entries read         2E equal
      10       15             30         30 True
     100      194            388        388 True
    1000     1992           3984       3984 True

exactly 2E entries read, the same as BFS: both are O(V + E).

What DFS is used for

Deciding whether a path exists. Cheaper to write than BFS when only reachability matters.

Connected components, chapter 96. Either traversal does it; DFS is the usual choice because the recursive form is three lines.

Cycle detection. If DFS reaches a vertex that is already on the current recursion path, there is a cycle. This is the standard method.

Topological sorting, the order of tasks that respect dependencies, built from the order in which DFS finishes with each vertex.

Maze solving and backtracking, which is DFS by another name: go down a corridor, and when it dead ends, back up to the last junction.

Finding articulation points and bridges, the vertices and edges whose removal disconnects a network. Beyond this syllabus, but it is DFS underneath.

BFS or DFS: the one line answer

Choose BFS when the question is about distance or nearness. Choose DFS when the question is about reachability, structure or ordering.

Quick revision

• DFS follows one path to its end, then backtracks; the structure is a stack.
• BFS and DFS differ in one line: dequeue from the front against pop from the top.
• The recursive order and the plain stack order DIFFER; push neighbours in reverse to make them agree.
• Both orders are valid depth first searches, so an answer should state its neighbour convention.
• A DFS depth is not a shortest distance: DFS recorded F at depth 3 when F is 2 edges away.
• Recursion costs one frame per vertex on a path, and it raised RecursionError on a 5,000 vertex path where the iterative version finished.
• O(V + E) time and O(V) space on a list, O(V squared) on a matrix: exactly 2E entries read.
• Uses: reachability, connected components, cycle detection, topological sort, mazes and backtracking.

Test yourself

1. What is the only structural difference between BFS and DFS? BFS takes the next vertex from the front of a queue; DFS takes it from the top of a stack. Everything else is the same.

2. Why do the recursive DFS and a stack DFS that pushes neighbours in listed order give different orders? A stack is last in, first out, so the last neighbour pushed is explored first, while the recursive loop explores the first neighbour first. Pushing the neighbours in reverse makes the two agree.

3. Can a DFS depth be used as a shortest distance? Give the evidence. No. On the chapter's graph DFS reached F at depth 3 by the route A, B, E, F, while the shortest route A, C, F is 2 edges.

4. State the time and space complexity, and the exact number of adjacency entries read. O(V + E) time and O(V) space on an adjacency list, O(V squared) on a matrix. Exactly 2E entries are read on an undirected graph.

5. Give one practical advantage of the iterative DFS over the recursive one. Its stack is on the heap, so it survives deep graphs. The recursive version raised RecursionError on a 5,000 vertex path that the iterative one traversed completely.

6. Name three problems DFS suits better than BFS. Cycle detection, topological sorting, and backtracking problems such as maze solving.

7. Which traversal answers "the fewest edges from A to B", and why? BFS, because its queue makes it visit vertices in order of increasing distance, so a vertex's level is its shortest distance in edges.