How does Depth First-Search visit a node?

2
votes

An algorithm may come upon a node a second time, i.e. there might be two paths to the node. The algorithm needs to know which path was shorter.

When the Best First Search reaches a node that it has visited before, it is possible that the previous visit had a longer path. When this happens, the open and closed lists need updating. This can not happen with an A* search.

Question: Can this happen with a DFS?

The answer is yes, but I thought it was no. Why is it yes? I thought that once a node has been visited it wont go back to it.

2
algorithmdepth-first-searchbreadth-first-searcha-star
This can not happen with an A* search. If heuristic is not optimal then A* will update that node with the cost which is shorter. So A* will manipulate things as well but if heuristic is optimal then it will not because we know there is no other node with cost less. - Luai Ghunim

2 Answers

3
votes

DFS strategy will visit a node as many times as it finds a path to it. It wouldn't continue visiting from that node down, but it would register the visit itself. This is essential for DFS edge classification.

For example, consider running DFS on this graph:

Graph

When you reach node C for the first time, the path is A-B-C. When you reach C for the second time, the path is A-C, which is shorter.

3
votes

If you have a graph like this

A
|\
B \
|  E
C /
|/
D

and traverse it depth-first, from left to right, the following pathes will be visited in that order:

A
AB
ABC
ABCD
AE
AED

You see, the first visit of D is on a longer path (ABCD) than the second one (AED).