# Data Structure Questions and Answers-Topological Sort

## Click on any option to know the CORRECT ANSWERS

 Question 1
Topological sort can be applied to which of the following graphs?
 A Undirected Cyclic Graphs B Directed Cyclic Graphs C Undirected Acyclic Graphs D Directed Acyclic Graphs

Question 1 Explanation:
Every Directed Acyclic Graph has one or more topological ordering whereas Cyclic and Undirected graphs can't be ordered topologically.

 Question 2
Most Efficient Time Complexity of Topological Sorting is? (V - number of vertices, E - number of edges)
 A O(V + E) B O(V) C O(E) D None of the mentioned

Question 2 Explanation:
The topological sort algorithm has complexity same as Depth First Search. So, DFS has a complexity O(V+E).

 Question 3
Topological sort starts from a node which has?
 A Maximum Degree B Minimum Degree C Any degree D None of the mentioned

Question 3 Explanation:
Topological sort starts with a node which has zero degree. If multiple such nodes exists then it can start with any node.

 Question 4
What can be the applications of topological sorting?
 A Finding prerequisite of a task B Finding Deadlock in an Operating System C Finding Cycle in a graph D All of the mentioned

Question 4 Explanation:
Topological sort tells what task should be done before a task can be started. It also detects cycle in the graph which is why it is used in the Operating System to find the deadlock.

 Question 5
Topological sort of a Directed Acyclic graph is?
 A Always unique B Always Not unique C Sometimes unique and sometimes not unique D None of the mentioned