Which of the following is true about BFS traversal (from a given source) of an unweighted, connected and undirected graph?

Question

BlackTom AI · Accepted Answer

BFS explores vertices in nondecreasing order of distance (number of edges) from the source, so it naturally computes shortest-path distances in an unweighted graph.

1) Relevant concepts
- Breadth-First Search (BFS) uses a queue and processes vertices level by level from the source.
- For an unweighted graph, "shortest path" means minimum number of edges.
- A vertex first discovered by BFS is at the minimum possible distance from the source.

2) Step-by-step reasoning (algorithmic outline)
- Initialize: dist[source] = 0; mark source visited; enqueue source.
- While queue not empty:
  - Dequeue u.
  - For each neighbor v of u: if v is unvisited, set dist[v] = dist[u] + 1, mark visited, and enqueue v.
- BFS processes all vertices at distance 0, then all at distance 1, then distance 2, and so on.

3) Intermediate logical steps / informal proof
- By induction on distance k from the source:
  - Base k = 0: source discovered with dist = 0.
  - Inductive step: assume all vertices at distance ≤ k are discovered with correct dist. Any vertex w at distance k+1 has a neighbor x at distance k (on a shortest path). That neighbor x is discovered and enqueued when BFS processes level k; when x is processed, w is discovered and assigned dist[x] + 1 = k+1. Thus w is discovered at its shortest possible distance.
- Contradiction argument: if BFS ever discovered a vertex at a distance greater than its true shortest distance d, then some vertex on a shortest path would have been discovered earlier and would have enqueued that vertex at distance d, contradicting the assumption.

4) Why the correct answer is correct
Because BFS explores level-by-level and assigns distances as dist[parent] + 1 the first time a vertex is seen, it guarantees those distances equal the minimum number of edges from the source — i.e., the shortest paths.

5) Why the other options are incorrect
- "A recursive BFS traversal would perform better": BFS is typically iterative with a queue; recursive variants are nonstandard and do not improve time complexity (still O(V+E)) and can worsen space/stack behavior.
- "BFS finds transitive closure": BFS from one source finds reachability from that source only; transitive closure (reachability for all pairs) requires running BFS/DFS from every vertex or Floyd–Warshall.
- "Sequences of vertices explored by BFS and DFS are always same": BFS and DFS use different strategies (level-order vs depth-first), so their exploration sequences generally differ.

6) Conclusion
Therefore, the correct statement is: "The paths found in the BFS traversal are the shortest paths from source to every other vertex," which matches the provided answer.

Which of the following is true about BFS traversal (from a given source) of an unweighted, connected and undirected graph?单项选择题

类似问题

In a breadth-first search of an undirected graph G, starting at vertex v, which of the following is true when the vertex w is found in level i?

In a breadth-first search of an undirected graph G, starting at vertex v, which of the following is true?

A complete graph is one where every two vertices are connected with an edge. Suppose we run BFS on a complete graph G(V,E) starting from some vertex s in V . What would the BFS layers look like?

Given a graph-G that has |V| vertices and |E| edges, that is:Connected. Directed. Weighted What is the worst case time complexity to run Breadth-First Search (BFS), if G is implemented using adjacency list?

What data structure is commonly used to implement Breadth-First Search (BFS)?

The below is a search tree, using breadth first search to reach goal Hamera. What is the answer ____.

更多留学生实用工具

智能学习助手

风格化写作助手

论文查重助手

文献引用助手

课堂转译助手

课堂笔记助手

Quiz搜索助手

学校历年真题

智能刷题助手

智能匹配练习

希望你的学习变得更简单