Order the nodes of a directed graph so that every edge points forward, like scheduling tasks after their prerequisites. Kahn’s algorithm repeatedly places a node with no unplaced prerequisites and “removes” its outgoing edges.
- Average time
- O(V + E)
- Space
- O(V)