Register

#Algorithms #DFS

• edited by
1,055 views
5 votes
5 votes

Consider the tree arcs of a $DFS$ traversal from a source node $W$ in an unweighted, connected, undirected 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.
• edited by
User Avatar

1 Answer

3 votes
3 votes

  • In example shortest path in graph from node w to c is 1 in  . But in DFS TREE . shortest path from node w to c is 2 . Hence option 1 and 2 are wrong.

  • In graph shortest path from w to leaf node E is 2 . But in DFS tree shortest path from w to leaf node E is 3 . So option 3 is  wrong

  • Option 4 is wrong.

I think none of the option are true.

User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
2
Subbu. asked Jul 16, 2022
359 views
#Dfs And Bfs
Please list the problems where BFS alone can do and DFS alone can do and both can do??
Please list the problems where BFS alone can do and DFS alone can do and both can do??
User Avatar
3 votes
3 votes
1 answer
3
Sunny123 asked Aug 7, 2016
2,083 views
#dfs
An undirected graph said to be hamiltonian if it has cycle containing all the vertices. Any DFS tree on a hamiltonian graph must have depth V-1 ? true of false
An undirected graph said to be hamiltonian if it has cycle containing all the vertices. Any DFS tree on a hamiltonian graph must have depth V-1 ? true of false
User Avatar
Link Copied!