Depth first search

Question

Consider the following graph G.

Modified DFS on G applied as follows:
• Starting vertex is ‘p’.
• Vertex is visited based on alphabetic order.
• Vertices are visited in order p, q, r, s, t, v.
• It works same as DFS except the visiting order restriction

What is the number of back edges during the above DFS traversal on G?

a. 2

b. 3

c. 4

d. 5

Explain...how??

Comments

4 should be correct ans.

(p,q) ,(p,s),(q,t) ,(v,t) are back edges and remaining tree edges.

---

How??

---

I am not sure about this...

I want to know is it the right way??

---

No.First make a DFS tree.

Then check for back edges.Now check this.

---

But it is not dfs

It is modified dfs

Nodes are examined in alphabetical order...

---

Yes but  in dfs we backtrack when  we don,t have choice.Here after visiting r we can,t backtrack because we have choice to select next vertex v.

Anyway back-edges will be 4 in all cases because In undirected graph dfs classify  every edge as tree edges or back edges.So tree edges will be n-1 and remaining back-edges.

---

@ManojK In dis figure for DFS d ordering is irrespective of d original graph mentioned in d ques. Isn't it Sir?

---

I think the order mentioned above qus in not correct .Its not following dfs property.

---

It is from made easy test

And they gave this order...

---

Ok let me check.

---

Yes check the similar qus from made easy.Qus no 24.

http://www.madeeasy.in/admin/ESEGroup/1PT_CS_16-07-16_Algo_1465.pdf

---

Yeah only graph is similar
Order is different

---

I think when we have choices than we need to give priority in this order (p,q,r,s,t,v). Means from P we have 3 choices either Q, R and S and we need to choose Q according to order. From Q, we have again 2 choices R and T. R should be given more priority. From R we have only one choice V(as P is already visited). So we should choose V. Similarly from V we have 2 choices either T or S and we should give priority to S first. From S to T.

Tree edges. (P, Q), (Q, R), (R, V), (V, S), (S, T).

---

Yes correct and remaining back edges.

---

Thank you Sir.