First time here? Checkout the FAQ!
0 votes

asked in Algorithms by Boss (6k points)   | 89 views

If i remove edge b/w B and E the graph is acyclic.

then apply DFS starts from vertex A.


It results two back edges D-C and E-B.

most cases it results only one back edge and in certain case like above it results two also.

Hence it results multiple back edges.

bt d-c is nt back edge it is cross edge
If some node is previously visited and we visit that node again then that edge is the back edge.

i missed it

Once u refer Coreman text book for DFS traversal,then u can easily understand.

parent node time intervals are u/v

and child is x/y then backside lies in b/w parent.i.e)u<=x<=y<=v   // condition for back edges.

so,whats the answer ..single or multiple??

1 Answer

0 votes

here is a result given in cormen book.....
A directed graph G is acyclic iff depth first search of G yields no back edges
i think b is correct

answered by Veteran (10.7k points)  

Top Users Jun 2017
  1. Bikram

    3704 Points

  2. Arnab Bhadra

    1502 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1481 Points

  5. junaid ahmad

    1432 Points

  6. Debashish Deka

    1384 Points

  7. Rupendra Choudhary

    1220 Points

  8. rahul sharma 5

    1220 Points

  9. Arjun

    1158 Points

  10. srestha

    1006 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. Arjun

    198 Points

  2. akankshadewangan24

    152 Points

  3. Debashish Deka

    138 Points

  4. Hira Thakur

    130 Points

  5. Soumya29

    104 Points

23,399 questions
30,111 answers
28,424 users