DFS , how to slove it?

Question

Comments

But there's a slight issue with the return times. For C)  Q ends before R which doesn't form a DFS sequence.

---

Yes, finish time of R should be 8 and that of Q should be 7.

 @Raveena Yadav 1

Take a time stamp counter, increment it when you discover(enter) a vertex and when you finish(leave) a vertex. Start with R and you will finish at R only.

According to the question, you should start that counter to 0.

---

In option A : S is disconnected because that is pushed and popped irrespective of anything onto the stack.

In option B : Q and R connected P and S has degree 0 (not connected to anyone)

In option C : It should be <(4,5),(2,7)(1,8),(3,6)> then everyone will be connected .

In option D : all are disconnected.

Answer 1

The problem is Solved by Using Strongly Connected component by Calling DFS.

      Call DFS for each option according to there start and Finish time.(<U,V> meaning U is starting time and V is finish time  of vertex)

1)  <(1,6) (2,5) (3,4) (8,10)>:  This option having 2 connected    component as 1/6,2/5,3/4 and 8/10 so not connected graph

2)   <(6,7) (2,5) (3,4) (8,9)>: In this graph having 3 connected component like (2/5,3/4) as one component,(6/7) is second and (8/9) is third component so it also not connected graph.

3)  <(4,5) (2,8) (1,7) (3,6)>: In this graph is connected as having single connected component as 1/8,2/7,3/6,4/5.

4) <(7,8) (1,2) (5,6) (3,4)> : graph having 4 connected component as (1/2),(3/4),(5/6),(7/8).

option C is correct.

Comments

why is 2 is finishing before 1? Isn't that should be (2,7) and (1,8)?

Answer 2

In DFS we will use stack and it is implemented as

option A:

First P will be discovered since it has the least discovery time

Now from P it will go to Q and then R and then R finishes at 4 and next Q finishes at 5 and P finishes at 6

In between there is no discovery of S so it cant be reached, So it is disconnected.

Option B:

It starts from Q and reches R and both gets finished . P and S are disconnected since they cant be reached.

Option C:

It starts from R and then Q and then S and then P So all can be reached. So connected.

Option D:

All are disconnected

Comments

Plzz Any one tell me how to solve this type of problem

---

@bhavnakumrawat4: See, analyze the pattern, that if you start visiting node with and if graph is connected then you will see all numbers consecutively, i.e. 1->2->3->4 as their starting point and 5->6->7->8 as their later ending point. Why?? Because they all are connected so as per DFS, it will go deep to explore all nodes but none of them will finish first till all are explored.

If they finish before exploring other nodes, definitely they are not connected i.e. like (1,2) so here graph at some point started at 1 and finished exploring at 2 without going deep, Why?? because it is not connected to any other node in graph.

---

Thanks

---

Thank you 😊