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.

--

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

RedHat Experts Session with Practical Implementation on Automation Using Ansible

Building Mobile Apps for Scale

How to Efficiently Merge Arrays in JavaScript

Change in environment configuration after the artefacts are built in Angular projects

React on Firebase

Persisted GraphQL Query with axios and SilverStripe 4

Sending an Email using EmailJS — Gmail Service to be used in Javascript

Caching in Simple

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
Adela Chao

Adela Chao

More from Medium

A for-dummies introduction to AWS-QLDB with an use case

Priority Based Round-Robin CPU Scheduling Algorithm with Case Study(Part-9)

Compiler Optimizations

How to Select a Graph Database: Best Practices at RoyalFlush