Kahn's algorithm produces a topological ordering of a directed acyclic graph by repeatedly removing a node that has no incoming edges from the remaining graph, appending it to the output order, and removing its outgoing edges, continuing until every node has been placed. If nodes remain with incoming edges after no more zero-indegree nodes are available, the algorithm reports that the graph contains a cycle and no topological order exists. It was described by Arthur B. Kahn in 1962 and runs in O(V plus E) time using a queue of currently available zero-indegree nodes.
Facts
Time Complexity Sources
1. Wikipedia: Topological Sort
Wikimedia FoundationAlgorithms section, Kahn's algorithm
One of these algorithms, first described by Kahn (1962), works by choosing vertices in the same order as the eventual topological sort.
Algorithms section, opening paragraph
The usual algorithms for topological sorting have running time linear in the number of nodes plus the number of edges, asymptotically, O(|V|+|E|).
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.