DFS Algorithm for undirected graph

Question

I am studying Depth First Search (DFS) on undirected graphs and I am confused about discovery order.

I have attached a figure of an undirected graph with DFS discovery (d) and finishing (f) times marked on each vertex.

In my traversal, vertex d directly discovers vertex e (there is an edge between them, and e is still unvisited when DFS is at d).

However, I have seen explanations suggesting that DFS must backtrack to an ancestor (like a) before discovering e, even though d is connected to e.

My questions are:

1. Is my DFS traversal and timing valid?

2. Can d directly discover e in DFS, or does this depend on adjacency list order?

3. Is there any DFS rule that forbids discovering e from d if an edge exists?

I want to be sure I am applying DFS rules correctly.

Answer 1

Your hand-drawn image is absolutely correct. In order to understand DFS, we need to understand that we always choose depth over breadth, so even though there is a vertex between a and e, the very fact that b was the "first" child to process, b's children are to be traversed before the other children of a. This is how c comes into the picture and then c's children are prioritized over the other children of ancestors, this is how we get to d and then finally d's children are prioritized over the siblings of ancestors.

This is an easy way to understand DFS:

• the first level is our starting point (a in your case)
• each level consists of the children of nodes in the previous level
• the children of a node are queued up to be processed
• there is also a stack (either an explicit one or the stack of memory if you implement recursively) where you stack up the nodes that are being processed, the top of which stack is the active level
• each item in the stack represents the active node of each level
• so if there is a Node N1 whose child of N2 is also a descendant of N3, which is also a child of N1, but N3 is evaluated among the children of N1 before N2, then N2 will be found/visited as a descendant of N3, before we would get to it as a child of N1
• depth-first essentially means that if N1 is being evaluated and there is an N2 node which is a sibling of N1 as well as its descendant on a given level, then, assuming N1 is found first, it is necessary that N2 will be found as a descendant first. The alternative, that takes breadth first is called BFS and it's another algorithm which has different priorities

Of course, since the children of a are b, c and e, from the image we don't see how they are to be queued up, so if e was the "first" queued child, then it would be the first to be processed after a.