self_doubt

Question

How to know no. of back edges in directed as well in undirected graph using DFS..can some1 tell some good source.??

Comments

Just do a DFS traversal of the graph.Those nodes visited first can be treated as ancestor and coming later can be treated as descendent .

So after doing DFS traversal , if in the graph u find the edges which are directed from descendent to ancestor in the graph w.r.t the DFS traversal done earlier , then such edges are referred to as back edges.

---

reference : Page 6 Images in this pdf

Answer 1

Tree edges which used in Dfs traversal.

Back edges ehich is goes already visited node ( condition here is it is ancestors)  in dfs traversal.

Comments

i am not able to paste the screen-shot here..can any1 suggest how to do?

---

oh..ya..sorry

u r ryt,there is no back edge concept in BFS.

so with cross edge and forward edge, cycle is possible by doing BFS?

---

In BFs case if cycle is thier then always cross edge present but vice versa no true since for cross edges are prsent in graph when no cycle.