Graph traversal

Overview

Recall questions on breadth-first and depth-first search, the queue and stack each depends on, why visited vertices are recorded, and tracing both on a small graph.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What does it mean to traverse a graph?

   Model answer

   To visit every vertex of the graph exactly once, following the edges, in a systematic order defined by the traversal algorithm. Because a graph may contain cycles, the traversal must record which vertices have already been visited so that it does not go round for ever.

2. 2

   Describe how a breadth-first search works.

   Model answer

   Start at a chosen vertex, mark it as visited and add it to a queue. Then repeatedly take the vertex at the front of the queue, examine each of its neighbours in turn, and for every neighbour not already visited mark it as visited and add it to the rear of the queue. Continue until the queue is empty. The effect is to visit all the vertices one edge from the start, then all those two edges away, and so on outwards in layers.

3. 3

   Describe how a depth-first search works.

   Model answer

   Start at a chosen vertex, mark it as visited and push it onto a stack. Then repeatedly look at the vertex on top of the stack: if it has an unvisited neighbour, mark that neighbour as visited and push it on top; if it has none, pop it and backtrack to the vertex beneath. Continue until the stack is empty. The effect is to follow one path as far as it will go before backtracking to try alternatives. It can equivalently be written recursively, with the call stack doing the same job.

4. 4

   Which data structure does each of breadth-first and depth-first search use, and why?

   Model answer

   Breadth-first search uses a queue. Because a queue is first in, first out, vertices are dealt with in the order they were discovered, so nearer vertices are always explored before further ones. Depth-first search uses a stack. Because a stack is last in, first out, the most recently discovered vertex is explored next, which drives the search deeper along one path and provides the backtracking when a dead end is reached.

5. 5

   A graph has vertices A, B, C, D, E, F and undirected edges A-B, A-C, B-D, C-E, D-F and E-F. Give the breadth-first traversal from A, taking neighbours in alphabetical order.

   Model answer

   A, B, C, D, E, F. A is visited and queued. Taking A, its neighbours B and C are visited and queued. Taking B, its unvisited neighbour D is visited and queued. Taking C, its unvisited neighbour E is visited and queued. Taking D, its unvisited neighbour F is visited and queued. Taking E, its neighbours C and F are already visited. Taking F, both its neighbours are visited, and the queue is empty.

6. 6

   Using the same graph — vertices A to F with edges A-B, A-C, B-D, C-E, D-F and E-F — give the depth-first traversal from A, taking neighbours in alphabetical order.

   Model answer

   A, B, D, F, E, C. From A the first unvisited neighbour is B, from B it is D, from D it is F, from F the unvisited neighbour is E, and from E it is C. C has no unvisited neighbours, so the search backtracks all the way, popping E, F, D, B and A in turn, and finishes.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.