Consider performing depth-first search (DFS) on an undirected and unweighted…
2024
Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at vertex 𝑠. For any vertex 𝑢 in G, 𝑑[𝑢] is the length of the shortest path from 𝑠 to 𝑢. Let (𝑢, 𝑣) be an edge in G such that 𝑑[𝑢] < 𝑑[𝑣]. If the edge (𝑢, 𝑣) is explored first in the direction from 𝑢 to 𝑣 during the above DFS, then (𝑢, 𝑣) becomes a ______ edge.
- A.
tree
- B.
cross
- C.
back
- D.
gray
Attempted by 272 students.
Show answer & explanation
Correct answer: A
Answer: tree
Why:
In DFS, an edge explored from a discovered vertex to an undiscovered vertex is classified as a tree edge; the undiscovered vertex becomes a child in the DFS tree.
The condition d[u] < d[v] indicates v is farther from the start s than u. If (u, v) is explored first in the direction u→v, v has not yet been discovered, so exploring (u, v) discovers v and the edge is a tree edge.
Other edge types (like back or cross edges) require the target to already be discovered (and in the case of back edges, to be an ancestor), which does not hold in this scenario.