patternMinor
How does DFS produce MST and All pairs shortest paths in unweighted graphs?
Viewed 0 times
produceshortestalldfspathsunweightedgraphsmstdoeshow
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#52259, answer score: 4
Revisions (0)
No revisions yet.