algorithm - 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.

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.