COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES
|
Question
[CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
|
Most Efficient Time Complexity of Topological Sorting is? (V-number of vertices, E-number of edges)
|
|
O(V + E)
|
|
|
O(V)
|
|
|
O(E)
|
|
|
O(V*E)
|
Explanation:
Detailed explanation-1: -Kahn’s algorithm is used to perform a topological sort on a directed acyclic graph with time complexity of O ( V + E ) O(V + E) O(V+E) – where V is the number of vertices and E is the number of edges in the graph.
Detailed explanation-2: -The time complexity of topological sort using Kahn’s algorithm is O(V+E), where V = Vertices, E = Edges.
Detailed explanation-3: -Explanation: We can implement topological sort by both BFS and DFS.
Detailed explanation-4: -Kahn’s algorithm for Topological Sorting-GeeksforGeeks.
Detailed explanation-5: -A topological ordering always starts with vertex whose indegree is zero and ends with vertex whose out-degree zero. Hence the correct answer is ABDC.
There is 1 question to complete.