Consider the following statements: Connected components of graph can be
Consider the following statements:
S₁: Connected components of a graph can be obtained by depth-first traversal but not by breadth-first traversal.
S₂: In DFS traversal every vertex of the graph is visited exactly once.
Which of the following options is correct?
- A.
Only S₁ is correct
- B.
Only S₂ is correct
- C.
Both S₁ and S₂ are correct
- D.
None of the statements is correct
Attempted by 97 students.
Show answer & explanation
Correct answer: D
Answer: None of the statements is correct.
Why the first statement is false: Both breadth-first search (BFS) and depth-first search (DFS) can be used to find connected components. The standard procedure is to iterate over all vertices and, for each vertex not yet visited, start a BFS or DFS; all vertices reached by that run form one connected component.
Why the second statement is false: As written, the claim is inaccurate. A single DFS started from one vertex visits only the vertices in that vertex's connected component. To ensure every vertex of a possibly disconnected graph is visited, you must start DFS from each unvisited vertex. With a proper DFS implementation that uses a visited set and performs a complete traversal (starting new DFS calls for unvisited vertices), each vertex will be discovered (processed) exactly once overall, although adjacency edges may be inspected multiple times.
Corrected statement for S1: Connected components can be obtained by either BFS or DFS by running the traversal from every unvisited vertex.
Corrected statement for S2: If DFS is implemented with a visited set and you perform a full traversal (starting DFS from each unvisited vertex), then each vertex is discovered exactly once during that complete traversal.