I have the following graph that I need to simulate a depth-first search of; starting at g:
My question is: How definite of an order is there when performing a depth-first search? When doing a DFS of a tree, I always see the left-most child searched first (completely), then after backtracking, the second-most-left child…
But with a graph, "left" seems a lot more arbitrary.
For the above graph, I got the following order:
g, j, i, m, n, o, k, h, p, l, e, a, f, c, b, d
But along the way, I found that there were many other possible paths to take. I'm guessing when implementing a DPS, I would visit the vertices in the order that they appear in the adjacency list (providing I'm using an adjacency list), but I don't have such information here.
Am I right that there are many possible answers to this question? And is my trace of the DPS correct?
Best Answer
Yes, there is no 'natural' ordering of the nodes of a graph. So there is also no 'natural' ordering in the result of the DFS of a graph.
Of course, in the example above, you could sort the nodes alphabetically as you have labels on them. If you assume that you have an order of the nodes, you can create a deterministic result of a DFS for example by always visiting lower nodes first.