Consider performing depth-first search (DFS) on an undirected and unweighted graph \(G\) starting at vertex \(s\). For any vertex \(u\) in \(G\), \(d[u]\) is the length of the shortest path from \(s\) to \(u\). Let \((u, v)\) be an edge in \(G\) such that \(d[u] < d[v]\). If the edge \((u, v)\) is explored first in the direction from \(u\) to \(v\) during the above DFS, then \((u, v)\) becomes a ______ edge.
Answer
(A)
Explanation
In a DFS of an undirected graph, every edge ends up as either a tree edge or a back edge. Cross (and forward) edges cannot occur: a vertex finishes only after all of its edges have been explored, so the far end of a newly explored edge is never already finished. Gray is the colour of a vertex that is discovered but not finished, not a kind of edge. So (B) and (D) are out.
The key reads "explored first in the direction from \(u\) to \(v\)" as the search moving from \(u\), the end nearer to \(s\), along this edge out to \(v\). DFS moves along an edge only to a vertex it has not discovered yet, so \(v\) is discovered through \((u, v)\) and the edge becomes a tree edge. A back edge, (C), would need \(v\) to be discovered already, and then the search does not move to \(v\) at all.
Answer: A