# Graph Topological Sort — Kahn’s Algorithm

2 min readMar 31, 2021

--

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**