During a Depth-First Search (DFS) on a directed graph G, the following edges are traversed:
- Edge (u, v), where v has already been visited and fully explored.
- Edge (x, y), where y has been visited but not fully explored yet.
- Edge (a, b), where b has been fully explored, but belongs to a different branch from a in the DFS tree.
Of course, each edge is traversed when it origin node is being explored. Which of the following options correctly classifies these edges according to their type in a DFS traversal?
A) (u, v) is a forward edge, (x, y) is a back edge, (a, b) is a back edge.
B) (u, v) is a cross edge, (x, y) is a forward edge, (a, b) is a tree edge.
C) (u, v) can be a forward or cross edge, (x, y) is a back edge, (a, b) is a cross edge.
D) (u, v) is a back edge, (x, y) is a cross edge, (a, b) is a forward edge.
E) None of the above
Original Idea by Sergio Sanchez
No comments:
Post a Comment