Graph Topological Sort — Kahn’s Algorithm

In another article (Graph Topological Sort — JavaScript implementation) I implement topological sort using DFS, here is the implementation of Kahn’s Algorithm, inspired by this tutorial video:

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.

Example Graph

• 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.

JavaScript Implementation