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

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.