Software Engineering
graph search
Updated Thu, 28 Jul 2022 08:09:06 GMT

How definite of an order is there to a depth-first search of a graph?


I have the following graph that I need to simulate a depth-first search of; starting at g: Graph

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?




Solution

Am I right that there are many possible answers to this question? And is my trace of the DPS correct?

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.