Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.2k views
in Technique[技术] by (71.8m points)

algorithm - Topological order using bfs

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.

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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). DAG

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...