Skip to content
Skein

Kahn's algorithm

RU: алгоритм Kahn

A topological sort that computes every vertex's in-degree, enqueues all in-degree-0 vertices, then repeatedly dequeues one into the output and decrements its neighbors' in-degrees, enqueuing any that reach 0. If the output has fewer vertices than the graph, a cycle exists. Runs in O(V + E).

shortcutsexpand
search
⌘K
prev piece
k
next piece
j
cycle tier
t
this menu
?