Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A depth first search produces a spanning tree. If you perform DFS using all possible orderings of the adjacency list, wouldn't you find the minimum spanning tree? In other words, there is no example of a graph where a DFS won't find the minimum spanning tree regardless of how the adjacency list is ordered. Is this correct or not? I can't come up with a counter example and intuitively it seems correct...

share|cite|improve this question
Sure, if you try all possible searches you'll find the minimum spanning tree, it's just inefficient. – Luke Mathieson Nov 19 '12 at 0:45

No you wont. Suppose you have as graph the complete graph $K_n$ with $n\ge 4$, for simplicity we pick the $K_4$, but this construction works for all larger $n$.

Every DFS-tree of a complete graph is a path, no matter how you order the edges. But clearly you can define the weights such that a non-path is the MST. See the example below (MST in red).

enter image description here

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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