Practice question · Put in order
Order the steps of breadth-first search from a start vertex.
- Visit each unvisited neighbour, marking it and adding it to the queue
- Repeat until the queue is empty
- Put the start vertex in the queue and mark it visited
- Remove the front vertex from the queue
Hints
- BFS uses a queue: first in, first out.
- You dequeue a vertex before you can look at its neighbours.
Show the answer
- Put the start vertex in the queue and mark it visited
- Remove the front vertex from the queue
- Visit each unvisited neighbour, marking it and adding it to the queue
- Repeat until the queue is empty
Why
BFS seeds the queue, then repeatedly dequeues a vertex and enqueues its unvisited neighbours, rippling outward level by level. The FIFO queue is what produces the level-order and the shortest paths.
Practise Graph Algorithms and Traversal
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Graph Algorithms and Traversal
- Swapping the queue in breadth-first search for a stack turns it into depth-first search, changing what the…
- A graph traversal on a graph with cycles runs forever without a visited set. Why does the set fix it, and…
- Select every true statement about graph traversal.
- Sort each task by which traversal is the natural fit.