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/