Test Datastructure

Question

We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes. Which of the following statements is(are) true?

I. We can use Depth First Search to determine the length of the shortest path between the pair of nodes.
II. We can use Breadth First search to find the desired answer.
III. Breadth First Search will give the correct answer only if the given graph is a tree.
IV. Depth First Search will give the correct result only if the given graph is a tree.

1. Only I and II
2.  Only II and IV
3. Only III and IV
4.  Only II and III

Comments

Ans 2) ?

---

should be 2 only mam

---

FIRST AND THIRD ARE CLEARLY WRONG SECOND IS RIGHT....  BUT I HAVE A DOUBT REGARDING FOURTH ONE THAT IT SAYS ABOUT TREE AND IN TREE THERE IS UNIQUE PATH FROM ANY NODE TO ANY NODE SO IRRESPECTIVE OF DFS AND BSF SO IT WILL BE CONSIDER AS TRUE OR NOT IF WE CONSIDER A CYCLE OF LENGTH FOUR AND THEN APPLY DFS IT WILL GIVE CORRECT ANSWER BUT ALL GRAPH CONTAINS CYCLE DO NOT SATISFY THE PROBLEM SO FOR GRAPH IT IS FALSE CLEARLY BUT ONLY TREE WILL MAKE IS FALSE OR NOT???

---

Yes mam 2) is answer I know that we can find shortest path from source to every vertices ,but i couldn't understand this question

please explain it :)

Answer 1

 We are provided with an undirected connected graph such that weight of all the edges is equal to some constant k. We wish to find the shortest distance between given pair of nodes.

Now we know that BFS is used to find the shortest distance between one node to every other node no matter it contains cycle or not Time will be O(e+v) only.

Now Take each statement:

I. We can use Depth First Search to determine the length of the shortest path between the pair of nodes.  It may be the case DFS fails i.e. when a graph has cycle then DFS may result incorrect i.e.

It can give distance between 2 - 5 as 2,1,4,3,5 = 4  which is incorrect , correct is 2,6,5 = 2.
II. We can use Breadth First search to find the desired answer. This is true since we go level by level so we will get the shortest path between every other node from a particular node.

III. Breadth First Search will give the correct answer only if the given graph is a tree. This is note true since for cyclic graph also we will get correct answer.

IV. Depth First Search will give the correct result only if the given graph is a tree. This is true since there is no cycle in graph i.e.tree so we have only one way to reach desired node i.e. we will get correct distance only.

Comments

@prashant sir I understood all the option except 2 

I read that -> in bfs we can find the shortest path from source to every other vertex

But in question it is given that we have to find the shortest path between given pair of nodes.

Now  i drawn the bfs tree for above connected graph that you have drawn then then in that bfs tree only from source vertex to other vertex we can find the shortest path if i want to find shortest path from 6 to 3 then in bfs tree it will be 4 but in actual graph it is 1 

Sir please , explain this option 

And correct me if i am making any mistake in understanding the question

 

---

if you want find the distance between U and V

then run BFS with starting node U...

 

read my comment in srestha mam answer

---

Prince, Then you have to start with 6 not with 1.

BFS find the shortest path from 1 to every other vertex because we start with 1. in order to find 6 to 3 shortest path you need to start with 6. Hope its clear your doubt.

---

Ok sir means this is the way ok now I got it :)

---

@shaikh sir I understood now, thankyou very much for this

i thought that only we have to do it one time but yes we can find shortest distance between any pair of nodes starting from that particular vertex from which we want to find the shortest path to desired vertex

Answer 2

Shortest distance of a graph can be found, when the graph forms a Minimum Spanning tree.(MST).

BFS is one of the way to find the path in tree format and definition of MST  is

"If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Minimum Spanning Tree". !

for more https://gateoverflow.in/3550/gate2006-it-11

Comments

Did you mean " clear explanation on this question "

---

Yes sir i am not getting that how bfs works

Here and in last option it is already a tree then what will be the role of DFS we can also do it by bfs .

---

Given that, all edges are same weight, therefore ignore the weight of edges... just you have a connected graph, ===> distance btw vertices = no.of edges btw them  

let you want to find the distance btw U and V

how bfs works ? 

start with U , in BFS, we add all adjacent nodes of it in the queue at a time, therefore until V encounter in to the queue. run the BFS

if V encounter in the first pass ( it happens when U and V are neighbors ) ===> distance btw them is 1 edge ==> cost = 1 * edge weight

if V encounter in the second pass ( it happens when U ---- X ------ V, where X is a any vertex in the graph except U and V ) ===> distance btw them is 2 edges ==> cost = 2 * edge weight

..... this process continues

 

 in last option it is already a tree then what will be the role of DFS we can also do it by bfs .

read that option clearly....  it is not saying " If tree, then DFS gives correct results ( it is true but there is no significance of DFS )"

it is saying " If DFS gives correct results then it must be a tree " 

 

Now my question arises,

WHY DFS doesn't gives correct results when given graph is not a tree ?

if you know this, just leave it