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 Time Complexity
Time Complexity (category) Connections
In Field
Source Wikipedia: Topological Sort
Sources
1. Kahn's Algorithm (Wikipedia)
Wikipedia infobox: time complexity linearQuote, Wikipedia infobox: time complexity linear
linear
2. 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|).
In Group: Graph Traversal and Connectivity Algorithms, Lead
a topological sort or topological ordering of a directed graph is a linear ordering of its vertices
- In Field: Algorithms and Complexity Theory, Lead paragraph
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.