CODEWITHSUNDEEP
graph
Diana
Diana

Reputation: 1437

Draw the depth first search tree

I am trying to solve some problems from some paper exams and I have this problem:

Consider the graph G = (N,A) where N={a,b,c,d,e,f,g,h} and A is the following set of arcs: {(0,5),(5,4),(4,5),(4,1),(1,2),(2,3),(3,4),(4,3),(0,6),(6,7)} and I have to draw the depth-first search tree T for G with the root being 0

This is the graph:

enter image description here

I got the following tree:

enter image description here

and the answer is this one:

enter image description here

(for both cases above, please ignore the arrows) and I don't understand why. Anyone who can explain me what I'm doing wrong? Thanks!

Upvotes: 4

Views: 6835

Answers (1)

Codor
Codor

Reputation: 17605

Both trees are correct in the sense that both of them can be generated by depth-first search. To my understanding, the key point here is that for a given graph, several depth-first search trees may exist, depending on the sequence in which children of the current node are selected. More precisely, depth-first search, without any clear rule on how to iterate children, is not a deterministic procedure. As indicated in the comments, the solution found by you can be obtained by selecting a child with minimum node index, whereas the proposed solution can be generated by selecting a child with maximum node index.

Upvotes: 0

Related Questions