Topological Sort

Orders the vertices of a directed acyclic graph so every edge points forward — the dependency order behind build systems, task schedulers and module loaders. Kahn's algorithm repeatedly emits a vertex with no remaining prerequisites; if the queue empties early, the graph contains a cycle.

Best

O(V+E)

Average

O(V+E)

Worst

O(V+E)

Space

O(V)