0
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Have you tried some examples? $\endgroup$ – Raphael Aug 10 '14 at 14:35
  • $\begingroup$ Yes I took a simple acyclic graph of 3 vertices.and tried to give the start and finish time as we do in DFS and the sorted them in non increasing order.There was a conflict.So I Just want to know if there is other way i Can modify BFS so that i can topologically sort vertices $\endgroup$ – monkey Aug 10 '14 at 14:44
  • 1
    $\begingroup$ The phrasing of your question does not reflect that you already know that BFS fails and have a proof. Please edit it accordingly. $\endgroup$ – Raphael Aug 10 '14 at 14:45
  • $\begingroup$ Perhaps you should check this tutorial. $\endgroup$ – Abdulkader Apr 11 '18 at 0:43
1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ A-->B A-->C B-->C and A-->B A-->C C-->B does it produce correct result for both cases. $\endgroup$ – monkey Aug 13 '14 at 6:04
  • $\begingroup$ This answer doesn't work. Consider the graph A->B B->C C->D D->E E->F A->E. This algorithm can output the ordering A B F C D E, which is incorrect -- that's not a valid topological sort. $\endgroup$ – D.W. Jul 8 '17 at 17:28
0
$\begingroup$

Yes, you can do topological sorting using BFS. Actually I remembered once my teacher told me that if the problem can be solved by BFS, never choose to solve it by DFS. Because the logic for BFS is simpler than DFS, most of the time you will always want a straightforward solution to a problem.

You need to start with nodes of which the indegree is 0, meaning no other nodes direct to them. Be sure to add these nodes to your result first.You can use a HashMap to map every node with its indegree, and a queue which is very commonly seen in BFS to assist your traversal. When you poll a node from the queue, the indegree of its neighbors need to be decreased by 1, this is like delete the node from the graph and delete the edge between the node and its neighbors. Every time you come across nodes with 0 indegree, offer them to the queue for checking their neighbors later and add them to the result.

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
  ArrayList<DirectedGraphNode> result = new ArrayList<>();
      if (graph == null || graph.size() == 0) {
        return result;
      }

  Map<DirectedGraphNode, Integer> indegree = new HashMap<DirectedGraphNode, Integer>();
  Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();



  //mapping node to its indegree to the HashMap, however these nodes
  //have to be directed to by one other node, nodes whose indegree == 0
  //would not be mapped.
  for (DirectedGraphNode DAGNode : graph){
      for (DirectedGraphNode nei : DAGNode.neighbors){
          if(indegree.containsKey(nei)){
              indegree.put(nei, indegree.get(nei) + 1);
          } else {
              indegree.put(nei, 1);
          }
      }
  }


//find all nodes with indegree == 0. They should be at starting positon in the result
  for (DirectedGraphNode GraphNode : graph) {
      if (!indegree.containsKey(GraphNode)){
          queue.offer(GraphNode);
          result.add(GraphNode);
      }
  }


//everytime we poll out a node from the queue, it means we delete it from the 
//graph, we will minus its neighbors indegree by one, this is the same meaning 
//as we delete the edge from the node to its neighbors.
  while (!queue.isEmpty()) {
      DirectedGraphNode temp = queue.poll();
      for (DirectedGraphNode neighbor : temp.neighbors){
          indegree.put(neighbor, indegree.get(neighbor) - 1);
          if (indegree.get(neighbor) == 0){
              result.add(neighbor);
              queue.offer(neighbor);
          }
      }
  }
  return result;
}
$\endgroup$
  • 1
    $\begingroup$ This is Kahn's Algorithm. $\endgroup$ – KWillets Jul 8 '17 at 15:01
  • $\begingroup$ In particular, it's no longer breadth-first search; it's just something different. (See here for a description of Kahn's algorithm.) So I don't see how this answers the question. $\endgroup$ – D.W. Jul 8 '17 at 17:29
  • $\begingroup$ This is actually BFS. The "indegree == 0" could be seen as a level, each time we traverse a new level where the nodes have indegree of 0. $\endgroup$ – sheeeva wu Jul 8 '17 at 19:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.