Switching
April 19, 2024Question 10496 – Linked-List
April 19, 2024Graphs-and-Tree
|
Question 4
|
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.
|
Breadth first search; acyclic
|
|
|
Topological sort; acyclic
|
|
|
Breadth first search; cyclic
|
|
|
Topological sort; cyclic
|
Question 4 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
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
Correct Answer: B
Question 4 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
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