Dark Mode

427 views

0 votes

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.

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.

0

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 !!

0