kahn

Kanh’s Algorithm

An algorithm for topological-sort, useful when we don’t have access to attributes of vertices.

• Put vertices with in-degree of $0$ in $Q$
• Set counter to $1$
• While $Q\ne \varnothing$
  • Remove a vertex $v\in Q$
  • Set label of $v$ to counter
  • Increment the counter
  • For any edge $(v,w)$, decrement the in-degree of $w$
  • If ${\mathrm{deg}}^{-}(w)=0$, put $w$ into $Q$
• If counter is less than $n+1$, there must be a cycle! Since some vertices didn’t get labeled, they must be in the cycle.