Depth-first traversal

Going deep and backtracking, recursively and with a stack; tracing it and what it is used for.

A4.3Trees and graphsA level25 min

To traverse a graph is to visit every vertex that can be reached from a starting vertex, each exactly once. There are two standard ways to do it, and they differ in which vertex they go to next. Depth-first traversal goes as far as it can along one path before it backs up and tries another. It is how you would explore a maze with a piece of chalk: keep walking, and at a dead end go back to the last junction that still has a way you have not tried.

The idea

Starting at A, depth-first traversal does this:

1. Visit the current vertex and mark it as visited.
2. For each of its neighbours in turn, if that neighbour has not been visited, traverse depth-first from it.
3. When every neighbour has been tried, go back to the vertex you came from. This going back is called backtracking.

The visited marks matter. This graph has a cycle, A, B, E, D, A, and without the marks the traversal would go round it forever.

Recursive depth-first traversal

Step 2 says "traverse depth-first from it", which is the whole algorithm again, so depth-first traversal is naturally recursive. Module A2 showed that every call gets its own stack frame; here the call stack remembers the way back, so backtracking is simply a call returning.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

GRAPH = {"A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B"],
         "D": ["A", "E"], "E": ["B", "D", "F"], "F": ["E"]}

def dfs(vertex, visited, depth):
    visited.append(vertex)
    print("    " * depth + "visit " + vertex)
    for neighbour in GRAPH[vertex]:
        if neighbour not in visited:
            dfs(neighbour, visited, depth + 1)
    return visited

print(dfs("A", [], 0))

Run this in the simulator

The indent shows how deep the recursion is. From A it goes to B, then to C, which is a dead end. It backtracks to B, whose next unvisited neighbour is E, and from E goes to D. Both of D's neighbours are visited, so it backtracks to E and goes on to F. The order is A, B, C, E, D, F.

With a stack of your own

Recursion hides the stack. The same traversal can use a stack the program manages itself, which is how exam pseudocode often writes it, and it cannot overflow the call stack on a very large graph. Push the start. Then repeatedly pop a vertex; if it has not been visited, visit it and push its unvisited neighbours. They are pushed in reverse order, so the first neighbour ends up on top and is popped next, which gives the same order as the recursion.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

GRAPH = {"A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B"],
         "D": ["A", "E"], "E": ["B", "D", "F"], "F": ["E"]}

visited = []
stack = ["A"]
while len(stack) > 0:
    vertex = stack.pop()                          # take from the top
    if vertex in visited:
        print("pop", vertex, "already visited")
        continue
    visited.append(vertex)
    for neighbour in reversed(GRAPH[vertex]):
        if neighbour not in visited:
            stack.append(neighbour)               # push on to the top
    print("pop", vertex, " visited", visited, " stack", stack)
print(visited)

Run this in the simulator

As a trace table, with the stack written bottom to top so the top is on the right:

D is on the stack twice: A pushed it, and E pushed it again before the first copy was popped. The check when popping is what stops it being visited twice.

What depth-first traversal is for

• Navigating a maze. Treat each junction as a vertex and each passage as an edge. Follow one passage to its end before trying another, and backtrack at dead ends: the stack always holds the way back.
• Is there a path? Traverse from one vertex. If the other vertex gets visited, a path exists. Anything never visited is in a separate part of the graph.
• Finding cycles. In an undirected graph, reaching a visited vertex that is not the one you just came from means there is a cycle.
• Ordering jobs. In a directed graph of "must happen before" edges, listing each vertex as the traversal finishes with it, then reversing that list, gives an order in which the jobs can be done. This is a topological sort.
• Backtracking puzzles such as sudoku: make a choice, go deeper, and undo the choice when it leads nowhere.

Depth-first traversal does not find shortest paths. It first reached D by A, B, E, D, three edges, when D is one edge from A. The next lesson's breadth-first traversal fixes that.

Efficiency. Each vertex is visited once. With an adjacency list, each edge is examined once from each end, so the time grows with V + E. With an adjacency matrix, finding a vertex's neighbours means scanning its whole row, so the time grows with V².

Task: what can be reached

The graph in GRAPH is undirected and stored as an adjacency list: each vertex's neighbours, in the order to try them. Write a function dfs that traverses the graph depth-first from a start vertex, recursively or with your own stack, and records the order in which the vertices are visited. Try the neighbours in the order the list gives them. Print DFS order: followed by the vertices in the order visited from A, separated by single spaces. Then print not reachable: followed by every vertex that was never visited, in alphabetical order, separated by single spaces.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

GRAPH = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
    "G": ["H"],
    "H": ["G"],
}

visited = []

Challenges

1. Make dfs also count the edges it follows to reach a new vertex. How does the count compare with the number of vertices visited, and why?
2. Write has_path(start, goal) that stops as soon as goal is visited, and returns True or False.
3. Reverse every neighbour list. Does the DFS order change? Does the set of vertices reached?