A ______ takes a directed ______ graph G and produces a linear ordering of all…
2017
A ______ takes a directed ______ graph G and produces a linear ordering of all its vertices such that for every directed edge (v, w), the vertex v comes before the vertex w in the ordering.
- A.
breadth first search; acyclic
- B.
topological sort; acyclic
- C.
breadth first search; cyclic
- D.
topological sort; cyclic
Attempted by 71 students.
Show answer & explanation
Correct answer: B
The correct option is B (topological sort; acyclic). A topological sort provides a linear ordering of vertices for a Directed Acyclic Graph (DAG). It ensures that for every directed edge (v, w), vertex v always appears before vertex w in the sequence, which is impossible if the graph contains cycles.