DFS

Question

Consider the following graph G

 

modified DFS on G is as folows:

starting vertex is 'a'

vertex is visited on alphabetic order

vertices are visited in order a,c,d,.....

it works same as DFS except the visiting order restriction

Which of the following is not a back edge during above DFA traversal on G?

(a) {f,b}

(b) {e,a}

(c){d,a}

(d){c,a}

Comments

It's d

---

ohh,its a undirected graph .

Right , D).

---

Kapil sir plz explain

Answer 1

In a directed graph , DFS tree has 4 edges ==> tree edge, forward edge, back edge and cross edge .

But, in case of undirected graph , DFS tree has 2 edges ==> Tree edge and back edge (Forward edges and back edges cannot be distinguished and cross edges are not there.)

Hence, (f,b) and (a,d) are back edges .In case of directed graph, (e,a) is a cross edge , but they don' t exist here .

Also, (c,a) is a tree edge , and , hence , it is not a back edge.

Comments

see , how DFS works=>

when u r at A , then we get e , c , d simultaneously on the call stack, which means we can choose either of them .But as it says , we have to go alphabetically , then obviously C is the priority.

Same, apply for D , we have now, a,c,b on the call stack. a,c are done , son we can only choose b , if not , then we would have choosen a instead.

---

Okay.. I get it now... Thanku very much :-)

---

Why didnt u consider the edge F-C ?

it should also be a back edge .