4

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?

5

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.

2

Yes, the exact path of the search does depend on what starting point you choose and--every time you hit a node with multiple unvisited children--what order you choose to visit the children in. Most implementations of DFS will always choose the same order, but which order that is depends on details of the algorithm implementation and graph representation that normally don't matter too much. Finally, your trace for that graph looks like one a valid one to me.

Note that it's possible for a directed graph to have only one valid starting point (in the sense that no other would allow it to visit every node) and one available path, but that's only in the trivial case of a "straight line" graph.

0

As you have hypothesized and as others have confirmed, there isn't a single optimal answer to the question. That said, you can group all possible answers into equivalence classes, and then point out that some classes are better than others.

Because of the specifics of how you've formulated this problem, the most natural equivalence classes are "correct answers" vs "incorrect answers", so we don't get something very interesting from that. But consider a very similar question which is "given an (undirected?) graph, what is its Breadth First Ordering, starting at g?"

A template for all of the optimal answers might look like [{g}, {j, k, h, d}, {f, i, o, c}, {a, m, n, e, p, b, d}]. This template offers [g, j, k, h, d, f, i, o, c, a, m, n, e, p, b, d] as one possible answer, but also [g, d, h, k, j, c, o, i, f, d, b, p ,e, n, n, a] for example.

You could then take an answer like [g, j, k, h, f, d, i, o, c, a, m, n, e, p, b, d] and say that it's "one level out of order". [g, j, k, d, f, h, i, o, c, a, m, n, e, p, b, d] is also one level out of order, and thus would belong to the same equivalence set.

In contrast, an answer like [g, j, k, f, h, d, i, o, c, a, m, n, e, p, b, d] would be two levels out of order, and thus belong to a different equivalence set.

Alternatively, you could build a Hasse diagram of all the possible orderings, essentially providing a partial ordering over the answers saying certain answers are "better" than others.

0

Pseudo-code for a recursive DFS

DFS(graph, start node s):
    mark node s as explored
    for edge (s, v) in graph:
        if v not explored:
            DFS(graph, v)

Depth-first-search is recursive based on the idea of backtracking. It exhaustively searches unexplored neighbors of the current node if possible, else to walk backward. This backtracking nature indicates that DFS can be implemented using the data structure stack to store explored nodes.

The output order is actually decided by the order that one node is stored in the adjacent list. It depends on the for loop that which node is found earlier than others. Thus there are multiple possible output orderings.

-1

If your graph is a spatial one, look toward Z-Filling algorithms, and depending on your intent, Marching algorithms to direct your tree walk toward a particular goal or interest region.

  • 1
    Could you explain this a bit more? – user40980 Jul 5 '15 at 12:49
  • Your example network (or nodegraph) has some closed loops, and its edges are not directed - there are algorithms designed to visit all spaces in a predictable and efficient way, which may be useful in terms of designing a best-fit directed acyclic graph to suit your needs. At any rate, I do suggest that you look at 'half-edge structures' to see what I mean by 'directed' graph structures, as they cope with both directions, and can handle networks with the loops you proposed. – Homer Jul 22 '16 at 10:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.