A_____takes directed graph and produce linear ordering of all its
A_____takes a directed ______ graph G and produce a linear ordering of all its vertices such that for every directed edge in G, 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 87 students.
Show answer & explanation
Correct answer: B
Answer: B) Topological sort; acyclic
Explanation:
Topological sorting of vertices of a Directed Acyclic Graph is an ordering of the vertices
V1,v2,...vn in such a way, that if there is an edge directed towards vertex vj from vertex
vi , then vi comes before vj