Question

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph \( G \) is/are TRUE?

• A. A DFS tree of \( G \) is a Shortest Path tree of \( G \).
• B. Every non-tree edge of \( G \) with respect to a DFS tree is a forward/back edge.
• C. If \( (u,v) \) is a non-tree edge of \( G \) with respect to a BFS tree, then the distances from the source vertex \( s \) to \( u \) and \( v \) in the BFS tree are within \( \pm 1 \) of each other.
• D. Both BFS and DFS can be used to find the connected components of \( G \).

Hint:

BFS ensures that nodes are visited in order of increasing distance, making it suitable for shortest path calculations in unweighted graphs. DFS, on the other hand, explores as far as possible before backtracking, which helps in cycle detection and connected component identification.

Answer 1

The Correct Option is B, C, D

• Option (A) – Incorrect: A DFS tree does not necessarily produce a shortest path tree because DFS does not prioritize shortest paths; it explores as deep as possible before backtracking. DFS focuses on exploring one branch of the graph fully before backtracking, and it does not guarantee the shortest path between vertices.
• Option (B) – Correct: In DFS, any non-tree edge is classified as a back edge, forward edge, or cross edge in directed graphs. In an undirected graph, non-tree edges can only be back or forward edges. This classification helps to identify the relationship between nodes in the DFS traversal.
• Option (C) – Correct: In BFS, all edges connect vertices that are either at the same level or adjacent levels in the BFS tree. Thus, the distance between the two endpoints of a non-tree edge differs by at most 1. BFS explores nodes level by level, ensuring that all edges either connect nodes within the same level or to an adjacent level.
• Option (D) – Correct: Both BFS and DFS can be used to determine connected components by exploring all reachable nodes from an arbitrary starting vertex. Both algorithms explore a graph thoroughly and can identify all nodes that are connected, helping to determine the connected components of the graph.

Thus, the correct answers are (B), (C), and (D).