Topological Sort — Kahn's Algorithm

Order a directed acyclic graph so every edge points forward — by repeatedly peeling off nodes that have no remaining prerequisites (in-degree 0).

Time: O(V + E)

Space: O(V)

Uses: In-degrees + Queue

Graph: Directed Acyclic

Speed: 1000ms

Step 1 of 0100%

Waiting (in>0)

Ready (in=0)

Removing

Sorted

Ready queue (in-degree 0):

Empty

Topological order:

—

Time:O(V + E)

Space:O(V)

Data Structure:Queue

Detects cycle:Yes

Question 1 of 3

What does a topological sort produce, and when does it exist?

DSAverse

Graph Algorithms

Loading Graph Algorithms...

BFS Traversal

visited: 0 / 7