The search is started at the root (there may be several roots in case of the graph) to explore all nodes along every branch untill either a goal node is found or the last node has no children to visit. Then, the algorithm backtracks to the previous node to explore adjacent branch until the final node is reached.
Consider the following example of order in which the nodes are visited:
The algorithm starts from the root (1) to explore the left branch until the node (4) is reached, then it backtracks to node (3) and proceeds to node (5), from which, it, again, returns to (3) before going to (6). Since node (3) has no other descendants to visit from, the algorithm returns to node (2) in order to explore node (7) and etc. until the final (16) node is reached.
As one can see, we have to return to the parent nodes many times. For example, since there are 3 descendants of the third node, the third node will be returned 3 times. However, there are some advanced implementations of DFS that avoid returning to the parent nodes, and, thus, saving a lot of time and efforts!
To be ammended ...
No comments:
Post a Comment