Question

Consider the directed graph G = (V, E) where V is the finite set of vertices and E is the set of directed edges between the vertices. G may contain cycle but there is no self-loop, further G may not be strongly connected. Let G$^R$ be the graph obtained by reversing direction of all edges without changing set of vertices. Assume that BFS or DFS for any given vertex V of a graph will visit only the reachable vertices from V in that graph. Which of the following statement must always be true regardless of the structure of G?

• A. In G$^R$, BFS traversal from V will visit exactly the same set of vertices as the DFS from V in G.
• B. If U is a reachable vertex in the DFS of G from V then V is also a reachable vertex in the BFS of G$^R$ from U.
• C. If U is a reachable vertex in the BFS of G$^R$ from V then U is also a reachable vertex in the DFS of G from V.
• D. The order of vertices visited in the BFS of G$^R$ from V is the reverse of the order of vertices visited in the DFS of G from V.

Hint:

The most important takeaway for problems involving reversing graph edges (transposing the graph) is the duality of reachability: a path from u to v in G exists if and only if a path from v to u exists in G$^R$.

Answer 1

The Correct Option is B

Step 1: Understanding the Question:
The core concept is the relationship between reachability in a directed graph G and its "reverse" graph G$^R$ (also known as the transpose graph). If there is a path from vertex V to vertex U in G, what can we say about paths in G$^R$?
Step 2: Key Concept - Graph Transpose:
If we have a directed path from V to U in graph G, like V $\rightarrow$ A $\rightarrow$ B $\rightarrow$ ... $\rightarrow$ U, then in the graph G$^R$ where all edges are reversed, this path becomes V $\leftarrow$ A $\leftarrow$ B $\leftarrow$ ... $\leftarrow$ U. This is equivalent to a directed path from U to V in G$^R$: U $\rightarrow$ ... $\rightarrow$ B $\rightarrow$ A $\rightarrow$ V. Therefore, U is reachable from V in G if and only if V is reachable from U in G$^R$.
Step 3: Detailed Explanation:
Let's evaluate each option based on this key concept:
- (A) In G$^R$, BFS traversal from V will visit exactly the same set of vertices as the DFS from V in G.
The set of vertices reachable from V in G is not necessarily the same as the set of vertices reachable from V in G$^R$. So, this is false.
- (B) If U is a reachable vertex in the DFS of G from V then V is also a reachable vertex in the BFS of G$^R$ from U.
- "U is a reachable vertex in the DFS of G from V" simply means there exists a directed path from V to U in G.
- Based on our key concept, if there is a path from V to U in G, then there must be a path from U to V in G$^R$.
- If there is a path from U to V in G$^R$, then V is reachable from U in G$^R$.
- Since V is reachable, any complete traversal algorithm starting from U in G$^R$, such as BFS, will visit V.
- This statement is always true.
- (C) If U is a reachable vertex in the BFS of G$^R$ from V then U is also a reachable vertex in the DFS of G from V.
- "U is a reachable vertex in the BFS of G$^R$ from V" means there is a path from V to U in G$^R$.
- This implies there is a path from U to V in G.
- The statement claims there is a path from V to U in G. This is the reverse and is not necessarily true. So, this is false.
- (D) The order of vertices visited... is the reverse...
The traversal order depends on the graph structure and adjacency list implementation. There is no simple relationship like reversal between a DFS in G and a BFS in G$^R$. So, this is false.
Step 4: Final Answer:
The only statement that must always be true is (B), as it correctly describes the fundamental property of reachability in a graph and its transpose.