Application of DFS

Question

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

Is the above statement is valid ?

My doubt is what will be minimum cost spanning for unweighted graph?

Every spanning tree is an MST for unweighted graphs.So i think the first part of statement is true.

However we can,t find single shortest path using DFT then how we will find all pair shortest path ?Expain pls?

Source:http://www.geeksforgeeks.org/applications-of-depth-first-search/

Comments

Yes. Not only SSSP as well as all pairs shortest path cannot be evaluated by DFS.

They have made it wrong in the link

---

DFS  not for shotest path

Strating from a single node, it goes to longest path and then backtrack.

So. "the minimum spanning tree and all pair shortest path tree" both are not possible

Those are for dijkastra, bellman ford ,floyd warshall algo.

Answer 1

we use BFS to calculate the shortest path not DFS that is the advantage of BFS over DFS