Are there any rules to choose the first adjacent vertex to do graph traversal?

Question

Suppose that I have a directed graph like this, and I want to traverse by using Depth-first search method.

[D] <-- [C] <-- [A] --> [B]

I'm going to start out at the vertex A. The vertex A has two adjacent vertexes B and C.

I wonder, which vertex should I select first to traverse?

It can be A,C,D,B or A,B,C,D which one is correct? Are there any rules?

Answer 1

Short answer: No.

As there is no correct or canonical order of the vertices of a graph (in general), there also is no such order for the DFS algorithm.

A Graph stored as a data structure in the memory of a computer, always has some vertex order, due to the linear memory address space. Depending on the labels/properties you put on your vertices, you could use them to establish an explicit ordering criteria, e.g. their alphabetical or numerical order. In general, this might lead to more deterministic results, but won't benefit the runtime.

Depending on the data structure, it's memory layout and the target architecture the algorithm will be executed on, there might be orderings that increase e.g. data locality while traversing the graph, and thus can speed-up the execution of the algorithm.

Depending on the problem the graph models, there might be beneficial orderings for special cases. Think of a case where the DFS is used to search for some vertex with a given property and then aborts as soon as a matching vertex is found. If a probability for finding such a vertex could be assigned to each vertex, then traversing the vertex with the highest probability first would clearly be a good idea.

Answer 2

There are no rules. Either order is equally correct. However, sometimes an instructor will tell you to traverse nodes in a particular order, such as alphabetically; in that case, of course do what your instructor says. But without explicit instruction, you can iterate through adjacent vertices in whatever order you like.