Topological Sorting

Topological sorting in a directed acyclic graph (DAG) to ensure the path doesn’t defy order required. Hence the orderings/sortings are not unique.

The process of topological sorting is demoed here. Note they key here is to design the queues to keep records and the recursive property. This algo leverage DFS which is familiar and starts randomly.

Note the characteristics of V list and at component is still not quite clear.

An alternative is called Kahn’s algorithm, where the orders starts from beginning. There are two queues created, one to register and track the number of inbound nodes (bottom), the other a heap to pop from those with zero inbounds step by step. then the bottom bottom, the topological order is created accordingly.

Reflect above deep thinking/reasoning into codes below:

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.