Depth first search closed

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 ______________

Comments

it is 4.

---

how please elaborate.....

Answer 1

Definition of Back edge :- If v is an ancestor of u, then edge (u, v) is a back edge.

ref :- https://courses.csail.mit.edu/6.006/fall11/rec/rec14.pdf

Now, starting from point p next unvisited nodes {q,r,s} choosing based on alphabetical order. i.e. q

standing at node q next unvisited nodes { r, t} choosing based on alphabetical order. i.e. r

standing at node r next unvisited nodes { v} choosing based on alphabetical order. i.e. v

standing at node v next unvisited nodes { s, t} choosing based on alphabetical order. i.e. s

standing at node s next unvisited nodes {  t} choosing based on alphabetical order. i.e. t

All nodes are traversed, 

Back edges are as follow :- (t,v), (s,p) , (t,q) (r,p)

Number of back edges = 4.

Hence 4 is the answer.

Comments

Thats wht I said : The question is conflicting..

---

Point no 3 is not required in the question.

---

But then point 4 is there to necessitate its requirement..