Graph Topological Sort — Kahn’s Algorithm
- Repeatedly remove vertices without any dependencies from the graph and add them to the topological ordering array
- When one vertex is removed, its neighbors become free, so they are the candidates for the next removal.
- Keep removing vertices without dependencies until all nodes are processed, or a cycle is discovered.
- Counting the incoming degree of each vertex
incoming degree : how many edges point to this vertex
A’s incoming degree = 0
B’s incoming degree = 1
D’s incoming degree = 2
- A vertex without dependencies means its incoming degree = 0.
- Create a queue to store vertices without dependencies, and use an index to keep track the removal count, this index can be topological number associated to the removed vertex.
- When we visit a vertex and remove it, we decrease its neighbors incoming degree, if one’s incoming degree becomes 0, add it into queue.
- When queue is empty, either all vertices are removed or a cycle is encountered, that is, there are some vertices left without visit but their incoming degree will never reduce to 0 because they point to each other.