6
$\begingroup$

I was reading Application of DFS from here where I came to a statement which I cannot really understand. Would anybody mind explaining this to me.

For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree and all pair shortest path tree.

My doubt: Is there anything "Minimum spanning tree" for unweighted graph. I mean after all it is unweighted so what is sense of MST here? And I completely don't understand how DFS produces all pair shortest path. Would anybody mind elaborating this a bit.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Every spanning tree is an MST for unweighted graphs. $\endgroup$
    – Yuval Filmus
    Jan 25, 2016 at 6:09
  • $\begingroup$ Have you read the comments? Multiple readers have expressed doubt in item 1) (even though not many give any reasoning). $\endgroup$
    – Raphael ♦
    Jan 25, 2016 at 9:55

2 Answers 2

Reset to default
4
$\begingroup$

There are two claims here.

For an unweighted graph, DFS traversal of the graph produces the minimum spanning tree.

This is true; in unweighted graphs, every spanning tree is minimal since they all have the same number of edges, $n-1$.

A nitpick I'd have is "the"; they should write "a minimum spanning tree".

For an unweighted graph, DFS traversal of the graph produces the all pair shortest path tree.

This is false, it doesn't even produce a single-source shortest path tree. See here.

In general, an APSP tree may not even exist. There are $n(n-1)$ shortest paths to encode, and it would be quite the coincidence if they shared only $n-1$ edges. Which can happen, e.g. in acyclic graphs, but it is certainly not always true. I'll leave it to you to come up with a small counter example.

Improve this answer
$\endgroup$
2
$\begingroup$

Unweighted in your blog post is probably a typo for undirected. However, even under this interpretation the blog post is wrong. See this question regarding DFS and minimum spanning tree, for example.

Don't take blog posts too seriously.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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