Topological sorting is about DAG(Directed Acyclic Graph). The main idea of Kahn algorithm is to:
Repeatedly find the start node(no income path, in-degree is 0) and print it.
To find the start node, there are many ways. Given in-degree is the most convenient one. While sometimes we might need a map(hash map) to map the relationship of neighbours. To achieve the KANH algorithm, we can use BFS as followed steps:
- Put all the start nodes in the queue;
- Poll the nodes, find their children
- The child nodes of the polled node: in-degree – 1(because we deleted the polled node)
- Find the child node whose current in-degree is 0 as new start node then put in the queue
In graph which is built by nodes(child reference, label…), we shall firstly build a hashmap to map the node to the degree.
For graphs that are built by arrays(int), we can just use an array to store the degree.
But hash map is still the best choice for most problems.
A clear java solution: http://www.jiuzhang.com/solutions/topological-sorting/