Graph-traversal study guide

A method for tracing either algorithm

Begin by writing the starting vertex and an empty or clearly labelled visited record. Then inspect the connections from the current vertex in the order supplied by the question. The stated order matters when several choices are available, so do not silently rearrange adjacent vertices.

For BFS, maintain a queue. Mark the starting vertex as visited, place it in the queue, and repeatedly remove the front item. Inspect its unvisited neighbours, mark newly discovered vertices as visited, and add them to the back of the queue. Continue until the required target is found or there are no more vertices in the queue. A useful trace table can contain: step number, current vertex, newly visited vertices, queue contents, and the resulting path information.

For DFS, maintain a stack or follow recursive calls. Start at the chosen vertex, mark it visited, and select an unvisited connected vertex. Continue from that vertex before considering alternatives at the earlier level. If no unvisited choice remains, return to the previous vertex. A trace table can contain: step number, current vertex, visited vertices, stack or current path, and any backtracking.

Reasoning about the appropriate algorithm

Use BFS when the task asks for a shortest path in an unweighted graph. The key reasoning is that BFS completes the nearer layer before processing a more distant layer. Therefore, the first discovery of a reachable target occurs through a path with the fewest edges, provided the traversal is performed correctly.

Use DFS when the task is to navigate a maze. The algorithm can commit to one route, continue along it, and backtrack when that route cannot lead to the required outcome. This makes the order of choices and the return to earlier vertices central parts of the explanation. Do not replace this reasoning with the claim that DFS gives a shortest path.

Worked reasoning example

Suppose a graph starts at S, with S connected to A and B. If A leads to target T using more edges than the route from B to T, BFS still examines the layer containing B according to queue order and processes vertices by distance from S. The important conclusion is not simply which neighbour is listed first: it is that BFS explores by layers and is therefore appropriate for the shortest path in this unweighted setting. A DFS trace, in contrast, follows one available branch deeply. If that branch reaches a dead end, DFS backtracks and tries another branch, which matches maze navigation.

Self-check guidance

After completing a trace, check four points:

1. Is every visited vertex recorded only once?
2. For BFS, were vertices removed from the front and added at the back of a queue?
3. For DFS, was a branch followed deeply before backtracking?
4. Does the conclusion match the application: BFS for a shortest path in an unweighted graph, or DFS for navigating a maze?

In an exam explanation, name the traversal, describe its order of exploration, identify the relevant data structure or backtracking behaviour, and connect that mechanism directly to the stated application.