algorithmgraph-algorithmdepth-first-search
Depth First Search - Advantages of traversing random neighbours
Depth First Search allows to traverse adjacent vertices in an arbitrary order. Are there any advantages in choosing random neighbours vs choosing neighbours in ascending fashion?
Consider the exploration order of following graph:
0 -> 9 -> 8 -> 7 ..
0 -> 1 -> 8 -> 7 ..
Can random choice lead to more favourable results?
Solution
Can I find a situation in which there is an advantage?
Yes. Easily. If I have a connected graph, traversing with random choices is guaranteed to eventually reach every node. Traversing in order is guaranteed to eventually wind up in a loop.
Is there an advantage in general?
No. For example in the connected example, a simple "keep track of where we have been" makes both reach everything. Which one will find a target node first will be a question of chance.