Back Edge

Question

Comments

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??

---

https://gateoverflow.in/145735/dfs-back-edge

Answer 1

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