“Create a top-down breadth-first search algorithm flowchart: read graph G and start vertex s, mark s visited and enqueue it, then while the queue is nonempty dequeue a vertex, record it in traversal order, and mark and enqueue each unvisited neighbor. Output the traversal order and end.”
Comprenez les décisions qui le sous-tendent.
The start vertex is marked before it enters the queue, avoiding duplicate work.
Dequeueing the next vertex makes the traversal breadth-first rather than depth-first.
Each unvisited neighbor is marked and enqueued during processing of the current vertex.
The queue-empty condition is stated inside a subroutine so the rendered diagram remains compact.
Use this for an unweighted graph traversal or shortest-hop explanation. Add parent and distance updates when the diagram is used for shortest paths.
Questions fréquentes
Why does BFS use a queue?
A first-in, first-out queue processes vertices by layers from the starting vertex.
When is a neighbor marked visited?
It is marked when it is enqueued, before another vertex can enqueue it again.
Can this find shortest paths?
Yes, BFS can find shortest paths by edge count in an unweighted graph when distance and parent data are added.