Graph

Question

Also let me know the approach to find back edges, cross edges, forward edges,

How to solve these questions

Answer 1

starts with A, Now you have choice of B and D, according to Tie break rule B is choosen

Now you are at B, you have choice of E only,

Now you are at E, you have choice of C and G, according to Tie break rule C is choosen

Now you are at C, you have choice of A and G, but note that A already visited, therefore you have choice of G only.

Now you are at G, you can't go ===> control return to C

Now you are at C, you can't go (due to all adjacent vertices completed ) ===> control return to E

Now you are at E, you can't go (due to all adjacent vertices completed ) ===> control return to B

Now you are at B, you can't go (due to all adjacent vertices completed ) ===> control return to A

Now you are at A, you have choice of D only,

Now you are at D, you have choice of F only,

Now you are at F, you can't go (due to all adjacent vertices completed ) ===> control return to D

Now you are at D, you can't go (due to all adjacent vertices completed ) ===> control return to A

Now you are at F, you can't go (due to all adjacent vertices completed ) ===> DFS travel over.

Now your DFS tree look like as

Note that there is no difference between right and left ( As we did in Binary trees )

Now take every edge of Graph G

(A,B) ===> part of DFS tree ===> it is Tree Edge

(A,D) ===> part of DFS tree ===> it is Tree Edge

(B,E) ===> part of DFS tree ===> it is Tree Edge

(E,C) ===> part of DFS tree ===> it is Tree Edge

(E,G) ===> E is a Ancestor of G ===> it is Forward Edge

(C,A) ===> C is a Descendent of A ===> it is Backward Edge

(C,G) ===> part of DFS tree ===> it is Tree Edge

(D,F) ===> part of DFS tree ===> it is Tree Edge

(F,C) ===> F is neither Ancestor nor Descendent of C ===> it is Cross Edge

(F,G) ===> F is neither Ancestor nor Descendent of G ===> it is Cross Edge

totally, 6 Tree Edges ( due to 7 vertices ) + 1 Forward Edge + 1 Backward Edge + 2 Cross Edges exist in this graph G

 

For Directed Graph:-

total edges = Tree edges + Front Edges + Back Edges + Cross Edges

 

For Undirected Graph:-

total edges = Tree edges + Front Edges ( or Back Edges )

https://gateoverflow.in/279686/data-structure-doubt?show=279829#c279829

Comments

Thanks for this brilliant answer

---

I am not able to understand this concept clearly. Why BG and AG are not forward edges?

---

@rajatmyname

consider the edges in the original graph only.

---

Now I understood. Thankyou

---

There are no cross edges and forward edges in an Undirected graph.Either an edge is a Tree Edge or a Back Edge in an Undirected Graph

---

After performing you get a Tree, based on that tree, the edges of the graphs ( it is directed ) called as

1) Forward edge

2) Backward Edge

3) Cross Edge

4) Tree Edge

---

If I have option than I make this answer as a "best answer"

---

you have choice of B and D, according to Tie break rule B is choosen

 

We can also choose D ist right ??

---

There is a tie brake rule.. therefore you have to choose B only

---

@Shaik Masthan  

Highlighted point contradicting ur "undirected graph" statement. 

If some mistake in ur explanation then please explain me that highlighted point. 

If image have some mistake then please clear that to n give some reference too so that i can learn it from there.

---

in undirected graph, you can't distinguish an edge as Forward edge or Back edge.

---

@Shaik Masthan 

How cross edge in undirected graph ?

( u mentioned above )

can u give an graphical example. that will be helpful

---

sorry that can't possible !

i will update !

---

Not sure coz i haven't read any standard reference but i think back edge will be more precise coz what we call back edge is edge that contribute to cycle formation. So in my opinion it would be back edge.

( just flash some light on above statement )

---

so you want to pronounce it Back edge rather than Forward edge ?

it's upto you !

you can call it as Forward edge also, due if C-- A is back edge then A -- C is surely forward edge

---

okay.sure. thanx. @Shaik Masthan

Btw, u ll be Veteran soon..nice

congo :v

---

still lagged under many concepts, So, may be that title doesn't suits for me !

---

Its not all about concepts. It includes management, support and much more. n may be u deserves it hence u r getting it.

---

awesome explanation

---

@Shaik Masthan

Is this the only  possible answer or according to DFS Tree answers may vary.....

Ex: Suppose after traversing E , I decided to go G instead of C and then come back to E and go to C in that case edge C-->G become cross edge.