About Depth First Search (DFS) and topological sorting, assign true or false to the following statements:
I) The visited node order of the following graph and adjacency list, starting with s, is s a c e b d
III) if a topological sort exists for the vertices in a directed graph, then a DFS on the graph will produce no back edges
IV) A DFS in a directed graph always produces the same number of tree edges
V) Suppose we perform a DFS on a directed graph G. If we remove all the back edges found, the resulting graph is acyclic
a) I, II, III
b) II, III, V
c) I, III, IV, V
d) I, III, V
e) All statements are true
Original Idea by: Levy Chaves
Your question has a number of problems: (1) it does not introduce the alternative; (2) last alternative is not "None of the above". However, it is very insightful and makes people think outside of the box. I'll correct it and take it.
ReplyDelete