BFS in Topological Sorting(Kahn)

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:

  1. Put all the start nodes in the queue;
  2. Poll the nodes, find their children
  3.  The child nodes of the polled node: in-degree – 1(because we deleted the polled node)
  4. 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.

topo2

For graphs that are built by arrays(int[][]), we can just use an array to store the degree.

topo1

But hash map is still the best choice for most problems.

A clear java solution: http://www.jiuzhang.com/solutions/topological-sorting/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s