Graph Topological Sort — Kahn’s Algorithm

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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store