Breadth-first search
Breadth-first search of a graph from a source: queue, marking, visit order, search tree, distances in number of edges, unweighted shortest path and O(n + m) cost.
- 25 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Source: what is it?
Show the answer
The starting vertex of the traversal: it is at distance 0 from itself and the first to enter the queue.
The distances and the search tree depend on the source: changing the source changes the visit order.
Graph of 8 vertices, edges: A-B, A-C, B-D, B-E, C-F, D-G, E-G, F-H, G-H. Neighbours taken in alphabetical order, breadth-first search from D: in which order do the vertices leave the queue?
- D B G A E H C F
- D B A C F H G E
- D B G A E C H F
- D G B H E A F C
Show the answer
D B G A E H C F
D has the neighbours B, G (level 1). B adds A, E; G adds H (E is already marked): level 2 = A, E, H. A adds C, H adds F: level 3. D B A C F H G E is the depth-first traversal from D, which dives down a branch before coming back.
Breadth-first search uses a …: vertices leave it in the order in which they … it.
Show the answer
Breadth-first search uses a queue: vertices leave it in the order in which they entered it.
A vertex at distance k is always discovered before a vertex at distance k + 1, so it leaves before it.
Queue: what is it?
Show the answer
A structure where items are added at one end, the tail, and removed at the other, the head: first in, first out.
In the traversal, the vertices discovered first are handled first, which forces level order. With a stack instead, the result would be a depth-first traversal.