The topological sorting of any DAG can be done in ________ time.

Category: QuestionsThe topological sorting of any DAG can be done in ________ time.
Editor">Editor Staff asked 4 weeks ago

The topological sorting of any DAG can be done in ________ time.
 
(a) cubic
 
(b) quadratic
 
(c) linear
 
(d) logarithmic
 
I’m obligated to ask this question of Directed Acyclic Graph topic in division Graph of Data Structures & Algorithms I
 
This question was addressed to me during an interview.

1 Answers
Editor">Editor Staff answered 4 weeks ago

The correct choice is (c) linear
 
To explain: Topological sorting can be done in O(V+E), here V and E represents number of vertices and number of edges respectively.