Can I use breadth-first search for topological sorting?

Problem Detail: 

Can I use breadth-first search for topologicallly sort vertices and finding strongly connected components in a graph?

If yes, how can I do that? If not, why?

I tried with a simple acyclic graph of 3 vertices, gave the start and finish time as we do in DFS and then sorted them in non-increasing order. There was a conflict. The result was topologically sorted.

I find in all books that we use depth first search here. Is there any way that I can modify BFS so that I can topologically sort vertices?

Asked By : monkey

Answered By : samz

BFS for topological sort seems possible to me.

All we need to add to the baseline BFS is a stack. The idea is that in BFS, nodes are traversed by levels relative to the starting node. When we get to the level where none of the nodes have un-visited children, we know that these nodes will be the first to put in topological ordering. Then we look at their immediate predecessors, and we know that they will be second to put in topological ordering. And we look at a level above, and so on.

Here is a pseudo-code snippet that does this on a subgraph reachable from the start_node (it'd be straightforward to extend it to the entire graph):

# Returns a list of nodes in topological-ordering. def top_bfs(start_node):     queue = [start_node]     stack = []     while not queue.empty():         node = queue.dequeue()         if not node.visited:             node.visited = True             stack.push(node)             for c in node.children:                 queue.enqueue(c)         else:             # node's ordering should be lowered because previously visited.             adjustedNode = stack.remove(node)             stack.push(adjustedNode)      stack.reverse()     return stack 

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29040