Source code online books for professionals by professionals

Listing 5-9.  Iterative Deepening Depth-First Search
def iddfs(G, s):
    yielded = set()                             # Visited for the first time
    def recurse(G, s, d, S=None):               # Depth-limited DFS
        if s not in yielded:
            yield s
            yielded.add(s)
        if d == 0: return                       # Max depth zero: Backtrack
        if S is None: S = set()
        S.add(s)
        for u in G[s]:
            if u in S: continue
            for v in recurse(G, u, d-1, S):     # Recurse with depth-1
                yield v
    n = len(G)
    for d in range(n):                          # Try all depths 0..V-1
        if len(yielded) == n: break             # All nodes seen?
        for u in recurse(G, s, d):
            yield u 
Note
 
■
  if we were exploring an unbounded graph (such as an infinite state space), looking for a particular node  
(or a kind of node), we might just keep trying larger depth limits until we found the node we wanted.
It’s not entirely obvious what the running time of IDDFS is. Unlike DFS, it will usually traverse many of the edges 
and nodes multiple times, so a linear running time is far from guaranteed. For example, if your graph is a path and 
you start IDDFS from one end, the running time will be quadratic. However, this example is rather pathological; if 
the traversal tree branches out a bit, most of its nodes will be at the bottom level (as in the knockout tournament in 
Chapter 3), so for many graphs the running time will be linear or close to linear.
Try running iddfs on a simple graph, and you’ll see that the nodes will be yielded in order from the closest to  
the furthest from the start node. All with a distance of k are returned, then all with a distance of k + 1, and so forth.  
If we wanted to find the actual distances, we could easily perform some extra bookkeeping in the iddfs function and 
yield the distance along with the node. Another way would be to maintain a distance table (similar to the discover 
and finish times we worked with earlier, for DFS). In fact, we could have one dictionary for distances and one for the 
parents in the traversal tree. That way, we could retrieve the actual shortest paths, as well as the distances. Let’s focus 
on the paths for now, and instead of modifying iddfs to include the extra information, we’ll build it into another 
traversal algorithm: breadth-first search (BFS).

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
108
Traversing with BFS is, in fact, quite a bit easier than with IDDFS. You just use the general traversal framework 
(Listing 5-6) with a first-in first-out queue. This is, in fact, the only salient difference from DFS: we’ve replaced LIFO 
with FIFO (see Listing 5-10). The consequence is that nodes discovered early will be visited early, and we’ll be 
exploring the graph level by level, just like in IDDFS. The advantage, though, is that we needn’t visit any nodes or 
edges multiple times, so we’re back to guaranteed linear performance.
16