I have the following graph that I need to simulate a depth-first search of; starting at
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?