# Kahn's Algorithm **An algorithm for finding a [[Topological Sorting|topological sort order]] of the vertices of a [[Directed Acyclic Graph|directed acyclic graph]] by selecting vertices in sorted order.** ![[KahnAlgorithm.svg]] *Kahn's algorithm; vertices with no incoming edges have themselves and their outgoing edges removed* > [!Algorithm] > 1. Maintain an initially empty list `L` of sorted vertices and a set `S` containing all vertices with no incoming edge. > 2. While `S` is not empty, > 1. Remove any vertex `v` from `S`. > 2. Add `v` to `L`. > 3. For all neighbours `w` of `v`, > - Remove the edge `e(v, w)` from the graph. > - If `w` has no more incoming edges, > 1. Add `w` to `S`. > [!infobox] Kahn's algorithm > | | | |:------------------------------------ | ---------- | | ***Worst-case [[time complexity]]*** | $O(V+E)$ | > <br> **Kahn's algorithm** is an algorithm that finds a [[Topological Sorting|topological sort order]] of the vertices of a [[Directed Acyclic Graph|directed acyclic graph]] by processing the vertices of the graph in the final topological order it produces. That is, it continually chooses to process any vertices that *no other vertex leads to first* before any of its neighbours. The set of vertices with no incoming edges can be implemented as a [[set]], or with a [[queue]] or a [[stack]], as the topological sort of a directed acyclic graph is not necessarily unique.