Topological order using bfs

Question

The following question was found in Sedgewick and Wayne book about algorithms in java:

4.2.19 Topological sort and BFS. Explain why the following algorithm does not necessarily produce a topological order: Run BFS, and label the vertices by increasing distance to their respective source.

I was trying to prove it finding a counter example. But, everytime I try, I get a topological order. I mean, I don't understand why this not work: If the source of a vertex comes before it, why don't we have a topological order?

I think to prove it, we need to find a vertex that its source comes before, but I couldn't.

Anyone have a counterexample? Thanks in advance!

PS: this is not homework

@Edit: I've tried an hamiltonian path like 1 <- 2 <- 0 <- 3 <- 4, which gives 0 3 4 2 1, but changing the positions of 0 3 and 4 gives me a topological order (but, in the order that I obtained, it is not). I am not sure this is or not a topological order, then.

Nunnery

Related posts - Using BFS for topological sort, Topological search and Breadth first search, & Relationship between BFS and topological sort – Naturally

Answer 1

You cannot use BFS, because a node with a higher rank may have an incident edge with a lower rank. Here's an example:

Let's say you start BFS at the source (A).

With the algorithm you proposed, node D would come before node C, which is clearly not a topological order. You really have to use DFS.

Louannlouanna

What is the definition of rank? I only know rank for trees. And, D could come before C if it appears first on the A's adjacency list, right? – Nunnery

Rank can be thought of as the "level" that a node is processed in BFS. A would have rank 1, B and D would have rank 2, etc – Louannlouanna

@Nunnery if this solution worked for you, would you please accept the answer? That way others will know that the answer is true – Louannlouanna

Answer 2

Counter-example:

A -> B
A -> C
B -> C

BFS starting at A could find the nodes in order A-B-C or A-C-B, but only one of those is a topological sort.

Pierrette

Answer 3

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;
}

Johnsen