GATE CSE
First time here? Checkout the FAQ!
x
0 votes
94 views

asked in Algorithms by Boss (6.1k points)   | 94 views

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

then apply DFS starts from vertex A.

A-B-C-E-D.

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.
yes.bro.

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.8k points)  


Top Users Aug 2017
  1. ABKUNDAN

    4660 Points

  2. Bikram

    4366 Points

  3. akash.dinkar12

    3258 Points

  4. rahul sharma 5

    3042 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2410 Points

  7. just_bhavana

    2100 Points

  8. Tesla!

    1918 Points

  9. stblue

    1682 Points

  10. joshi_nitish

    1608 Points


24,928 questions
32,024 answers
74,385 comments
30,113 users