427 views
Consider the tree arcs of a DFS traversal from a source node W in an unweighted, connected, undirected, acyclic graph. The tree T formed by the tree arcs is a data structure for computing-
1. the shortest path between every pair of vertices.
2. the shortest path from W to every vertex in the graph.
3. the shortest paths from W to only those nodes that are leaves of T.
4. the longest path in the graph.

You can solve it by using just a simple example where all these condition satisfied unweighted, connected, undirected and acyclic in the result you observe the shortest path between every pair of vertices.

wrt me  No, you cannot use DFS to find shortest path in an unweighted graph. finding the shortest path between two nodes is  solved by BFS.   Shortest path from source to all other vertices is implemented by bfs.

I think none of the options is correct but If I have to choose one option then I choose 4) the longest path in the graph because in dfs what happens is we take a element for exploration and we start exploring it as the elmement find new element which is unexplored it leaves the element and start with that

therefore , It goes as far as it can from the source vertex and then returns back to unvisited adjacent nodes of visited vertices.

but in my opinions none of the options are correct

I'm not sure !!

NOTE THAT GIVEN GRAPH IS ALREADY TREE

1 vote