Breadth-first search (BFS) explores a graph outward from a starting vertex, visiting vertices in layers of increasing distance. Its orderly exploration makes it useful for finding shortest paths when path length is measured by the number of edges.
Start from a root or source vertex. BFS first visits that vertex, then visits its unvisited neighbors, then the unvisited neighbors of those vertices, and continues outward. Thus, all vertices at distance d from the source are explored before vertices at distance d+1.
All flashcards
What is breadth-first search?
BFS is a graph or tree traversal that begins at a source and explores reachable vertices in order of increasing distance from it.
What role does the queue play in BFS?
The FIFO queue stores discovered vertices waiting to be explored. Processing the earliest-enqueued vertex first keeps the search moving through one distance layer at a time.
Why mark a vertex explored when it is enqueued?
It prevents the same vertex from being added to the queue multiple times, especially in graphs with cycles or multiple paths to a vertex.
How do parent links help after BFS finds a goal?
Each parent link records how a vertex was first reached. Following these links backward from the goal reconstructs a shortest path to the source in an unweighted graph.
How does BFS differ from DFS?
BFS explores all vertices at the current distance before moving farther away, using a queue. DFS follows a branch deeply before backtracking, typically using a stack or recursion.
Quiz questions
What does it mean for a search algorithm to be complete?Answer: It is guaranteed to find a goal whenever one exists, under the search assumptions.
When BFS runs on a directed graph, which edges can it follow?Answer: It follows outgoing edges in their permitted direction from the source.
What can cause two valid BFS orderings of the same graph to differ?Answer: Different choices for the order in which neighbors are processed.
How can BFS help test whether a graph is bipartite?Answer: Assign alternating colors by layer and check whether every edge joins different colors.
For a finite graph, what is the worst-case auxiliary space complexity of BFS?Answer: O(∣V∣)