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

asked in Algorithms by Boss (6.5k points) 8 118 248 | 103 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 (11.8k points) 13 43 139

Related questions

+1 vote
1 answer
2
asked in Algorithms by Salman Active (1k points) 5 10 20 | 134 views


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23684 Points

  2. Bikram

    17288 Points

  3. Habibkhan

    9194 Points

  4. srestha

    6486 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5168 Points

  7. Sachin Mittal 1

    4910 Points

  8. joshi_nitish

    4504 Points

  9. sushmita

    4080 Points

  10. Rishi yadav

    3998 Points


Recent Badges

Nice Comment Pooja Palod
Famous Question Harsh181996
Verified Human ASK
Good Comment Bikram
Good Comment Arjun
Nice Comment Arjun
Famous Question Meenakshi Sharma
Famous Question Meenakshi Sharma
Nice Question smartmeet
Nice Comment Vicky rix
27,426 questions
35,275 answers
84,602 comments
33,523 users