Questions: Breadth-First Search: Implementation and Applications

Question 1

A graph has vertices A, B, C, D where A connects to B and C, B connects to D, and C connects to D. Starting BFS from A, you want the shortest path to D. Which sequence does BFS guarantee?

• A. A → B → D, because BFS explores the first neighbor it finds
• B. A → C → D, because alphabetical ordering determines BFS priority
• C. Either A → B → D or A → C → D — both have length 2, and BFS guarantees both are shortest
• D. A → B → C → D, because BFS visits all vertices before backtracking

Answer: (C)

BFS visits all distance-1 vertices (B and C) before any distance-2 vertices (D). Both B and C lead to D in one more hop, so both paths have length 2 — the shortest possible. BFS doesn't guarantee *which* length-2 path is returned (that depends on adjacency list ordering), but it guarantees the returned path has minimum length. Option D describes a longer path, and options A/B wrongly assume BFS has a preference beyond distance.

Question 2

You are testing whether a graph is bipartite using BFS. You color the source vertex red, its neighbors blue, their neighbors red, and so on. What condition indicates the graph is NOT bipartite?

• A. BFS reaches a vertex that has already been visited
• B. A vertex is about to be colored, but its already-colored neighbor has the same color
• C. BFS terminates before visiting all vertices
• D. A vertex has more neighbors of one color than the other

Answer: (B)

Bipartiteness means no edge connects two same-colored vertices. BFS assigns levels (distance from source), and a graph is bipartite exactly when every edge connects vertices at adjacent levels — never the same level. If BFS tries to assign a color to a vertex but finds an already-colored neighbor with the same color, an edge connects same-level vertices, which means an odd-length cycle exists, making the graph non-bipartite. Revisiting a vertex (option A) is normal and handled by the visited set; it doesn't indicate non-bipartiteness.

Question 3

BFS can find all connected components of an undirected graph by repeatedly starting BFS from any unvisited vertex until all vertices have been visited.

• T. True
• F. False

Answer: True

This is exactly how component detection works. A single BFS run from any vertex visits every vertex reachable from it — that's one complete connected component. When BFS finishes, any still-unvisited vertex must belong to a different component. Starting BFS from each unvisited vertex in turn discovers all components. The total work is O(V + E) across all BFS runs, since each vertex and edge is processed exactly once.

Question 4

In a weighted graph where edge weights represent distances, BFS finds the shortest path between any two vertices.

• T. True
• F. False

Answer: False

BFS minimizes the *number of edges* (hops) on a path, not the total weight. In an unweighted graph these are equivalent. But in a weighted graph, a path with fewer edges may have greater total weight than a path with more edges. For example, a direct edge of weight 100 gives a shorter hop count than a two-hop path of total weight 3, but BFS would return the direct edge as the 'shortest' path. Weighted shortest paths require Dijkstra's algorithm (for non-negative weights), which generalizes BFS by using a priority queue ordered by accumulated cost rather than a plain FIFO queue.

Question 5

Why does BFS guarantee that the first time it reaches a vertex, it has found the shortest path to that vertex in an unweighted graph?

Model answer: BFS uses a queue, which enforces FIFO ordering. This means vertices are dequeued in non-decreasing order of their distance from the source: all distance-1 vertices are processed before any distance-2 vertex, all distance-2 before any distance-3, and so on. The first time BFS reaches vertex v, it arrives via a path of some length d. Since all shorter paths (length < d) have already been fully explored without reaching v, no shorter path to v exists. Any later path to v found by BFS would have length ≥ d.

The key is that a queue (not a stack) enforces level-by-level traversal. A depth-first search using a stack might reach a vertex via a long winding path before discovering the short direct path — DFS gives no shortest-path guarantee. The queue ensures BFS 'radiates outward' in uniform distance shells, so first contact = minimum distance.