Nonrecursive depth-first search

Since function calls are expensive, recursion can be slow. It also has the disadvantage that at any given instant of time only the current tree node is accessible. This could be a problem when we try to parallelize tree search by dividing tree nodes among the threads or processes.

It is possible to write a nonrecursive depth-first search. The basic idea is modeled on recursive implementation. Recall that recursive function calls can be implemented by pushing the current state of the recursive function onto the run-time stack. Thus, we can try to eliminate recursion by pushing necessary data on our own stack before branching deeper into the tree, and when we need to go back up the tree—either because we’ve reached a leaf or because we’ve found a node that can’t lead to a better solution—we can pop the stack.

This outline leads to the implementation of iterative depth-first search shown in Program 6.5. In this version, a stack record consists of a single city, the city that will be added to the tour when its record is popped. In the recursive version we continue to make recursive calls until we’ve visited every node of the tree that corresponds to a feasible partial tour. At this point, the stack won’t have any more activation records for calls to Depth_first_search, and we’ll return to the function that made the

original call to Depth_first_search. The main control structure in our iterative ver-sion is the while loop extending from Line 3 to Line 20, and the loop termination condition is that our stack is empty. As long as the search needs to continue, we need to make sure the stack is nonempty, and, in the first two lines, we add each of the non-hometown cities. Note that this loop visits the cities in decreasing order, from n-1 down to 1. This is because of the order created by the stack, whereby the stack pops the top cities first. By reversing the order, we can insure that the cities are visited in the same order as the recursive function.

Also notice that in Line 5 we check whether the city we’ve popped is the constant NO_CITY. This constant is used so that we can tell when we’ve visited all of the chil-dren of a tree node; if we didn’t use it, we wouldn’t be able to tell when to back up in the tree. Thus, before pushing all of the children of a node (Lines 15–17), we push the NO_CITY marker.

An alternative to this iterative version uses partial tours as stack records (see Program 6.6). This gives code that is closer to the recursive function. However, it also results in a slower version, since it’s necessary for the function that pushes onto the stack to create a copy of the tour before actually pushing it on to the stack. To emphasize this point, we’ve called the function Push_copy. (What happens if we sim-ply push a pointer to the current tour onto the stack?) The extra memory required will probably not be a problem. However, allocating storage for a new tour and copying the existing tour is time-consuming. To some degree we can mitigate these costs by saving freed tours in our own data structure, and when a freed tour is available we can use it in the Push_copy function instead of calling malloc.

On the other hand, this version has the virtue that the stack is more or less independent of the other data structures. Since entire tours are stored, multiple threads or processes can “help themselves” to tours, and, if this is done reasonably carefully,

Pppppppppppppppppp

it won’t destroy the correctness of the program. With the original iterative version, a stack record is just a city and it doesn’t provide enough information by itself to show where we are in the tree.