Source code online books for professionals by professionals

Figure 5-6.  Two traversals of a size four cycle. The depth-first tree (highlighted, left) will not necessarily contain 
minimal paths, as opposed to the shortest path tree (highlighted, right)
In keeping with the maze metaphor, let’s briefly take a look at another maze exploration algorithm, described by 
Øystein (aka Oystein) Ore in 1959. Just like Trémaux, Ore asks you to make marks at passage entries and exits. Let’s say 
you start at intersection a. First, you visit all intersections one passage away, each time backtracking to your starting 
point. If any of the passages you followed were dead ends, you mark them as closed once you return. Any passages 
leading you to an intersection where you’ve already been are also marked as closed (at both ends).
At this point, you’d like to start exploring all intersections two steps (that is, passages) away. Mark and go through 
one of the open passages from a; it should now have two marks on it. Let’s say you end up in intersection b. Now, 
traverse (and mark) all open passages from b, making sure to close them if they lead to dead ends or intersections 
you’ve already seen. After you’re done, backtrack to a. Once you’ve returned to a, you continue the process with the 
other open passages, until they’ve all received two marks. (These two marks mean that you’ve traversed intersections 
two steps away through the passages.)
Let’s jump to step n.
14
 You’ve visited all intersections n–1 steps away, so all open passages from a now have n–1 
marks on them. Open passages at any intersections next to a, such as the b you visited earlier, will have n–2 marks 
on them, and so forth. To visit all intersections at a distance of n from your starting point, you simply move to all 
neighbors of a (such as b), adding marks to the passages as you do so, and visit all intersections at a distance n–1 out 
from them following the same procedure (which will work, by inductive hypothesis).
Once again, using only local information like this might make the bookkeeping a bit tedious (and the explanation 
a bit confusing). However, just like Trémaux’s algorithm had a very close relative in the recursive DFS, Ore’s method 
can be formulated in a way that might suit our computer science brains better. The result is something called iterative 
deepening depth-first search, or IDDFS,
15
 and it simply consists of running a depth-constrained DFS with an iteratively 
incremented depth limit.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
107
Listing 5-9 gives a fairly straightforward implementation of IDDFS. It keeps a global set called yielded, consisting 
of the nodes that have been discovered for the first time and therefore yielded. The inner function, recurse, is 
basically a recursive DFS with a depth limit, d. If the limit is zero, no further edges are explored recursively. Otherwise, 
the recursive calls receive a limit of d-1. The main for loop in the iddfs function goes through every depth limit from 
0 (just visit, and yield, the start node) to len(G)-1 (the maximum possible depth). If all nodes have been discovered 
before such a depth is reached, though, the loop is broken.