Graph-traversal revision notes

What graph traversal means

A graph traversal is a systematic process for visiting vertices in a graph. The order in which vertices are visited depends on the traversal algorithm and the connections between vertices.

Breadth-first search (BFS)

Breadth-first search explores the graph in layers. It first visits the starting vertex, then all directly connected vertices, then vertices one connection farther away, and so on. A queue is used: a vertex is added to the back of the queue when it is discovered and removed from the front when it is processed. A record of visited vertices prevents the same vertex being processed repeatedly.

A trace should show the current vertex, the vertices discovered from it, the visited record, and the queue after each step. For example, if starting at A, and A is connected to B and C, BFS processes A before processing B and C. It then processes the next vertex in the queue before moving to vertices at a greater number of edges from A.

For an unweighted graph, BFS can find a shortest path: the path with the fewest edges between the starting vertex and a target vertex. This works because vertices are processed in increasing numbers of edges from the starting point. If a target is first reached through one path and another possible route contains more edges, the longer route is not the shortest path.

Depth-first search (DFS)

Depth-first search follows one available route as far as possible before returning to an earlier vertex and trying another route. It can use a stack, or an equivalent recursive process. A visited record is again important so that cycles do not cause the traversal to continue indefinitely.

When tracing DFS, identify the current path and follow the next unvisited connection. If there is no suitable unvisited connection, backtrack to the previous vertex. This makes DFS useful for navigating a maze, where the search can follow one route, return when that route does not work, and then explore an alternative route.

Important distinction

BFS is associated with finding a shortest path in an unweighted graph. DFS is associated with exploring deeply and is useful when navigating a maze. DFS may find a route through a graph, but it should not automatically be described as finding the shortest route.

Common errors

• Confusing a queue used by BFS with a stack used by DFS.
• Describing BFS as exploring one complete route before trying another; that is depth-first behaviour.
• Forgetting to mark vertices as visited.
• Claiming that BFS finds the shortest path when edges have different weights; the specified shortest-path use is for an unweighted graph.
• Saying that DFS always finds the shortest path. Its typical application here is navigating a maze, not guaranteeing the shortest route.