Which of the following problems is guaranteed to be solved by a single…

Concept

Standard BFS uses a FIFO queue and visits vertices in nondecreasing distance layers from one source. In an unweighted graph, traversing one edge increases path length by exactly one, so first discovery fixes the minimum edge count.

A task that needs extra bookkeeping, a transformed graph, repeated traversals, or a different invariant is not guaranteed by one ordinary BFS traversal on the graph as given.

Application

1. Start at a source s, set distance(s) = 0, and enqueue s.

2. When a vertex at distance d is dequeued, every newly discovered neighbor is assigned distance d + 1 and enqueued.

3. Because the queue processes all vertices at distance d before any at distance d + 1, no later discovery can use fewer edges.

4. For example, if s is adjacent to a and b, and a is adjacent to t, BFS visits a and b at distance 1 and then t at distance 2; the parent links recover a minimum-edge path s–a–t.

Contrast

• Finding connected components in a directed graph is ambiguous between weak and strong connectivity; it requires ignoring directions, testing mutual reachability, or running additional traversals.

• Detecting cycles in a directed graph requires recursion-stack state or indegree processing.

• Topological sorting requires finishing-time ordering or repeated zero-indegree removal.

Cross-check and result

Each alternative needs an invariant beyond one standard BFS traversal. The guaranteed direct application is finding a shortest path in an unweighted graph.