Consider performing depth-first search (DFS) on an undirected and unweighted…
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 474 students.
Sign up free to check your answer
Sign up freeLoading lesson…