Source code online books for professionals by professionals

Listing 5-4.  Recursive Depth-First Search
def rec_dfs(G, s, S=None):
    if S is None: S = set()                     # Initialize the history
    S.add(s)                                    # We've visited s
    for u in G[s]:                              # Explore neighbors
        if u in S: continue                     # Already visited: Skip
        rec_dfs(G, u, S)                        # New: Explore recursively
Note
 
■
  as opposed to the 
walk
 function in listing 5-1, it would be wrong to use the 
difference
 method on 
G[s]
  
in the loop here because 
S
 might change in the recursive call and you could easily end up visiting some nodes  
multiple times.
Go Deep!
Depth-first search (DFS) gets some of its most important properties from its recursive structure. Once we start 
working with one node, we make sure we traverse all other nodes we can reach from it before moving on. However, as 
mentioned in Chapter 4, recursive functions can always be rewritten as iterative ones, possibly simulating the call stack 
with a stack of our own. Such an iterative formulation of DFS can be useful, both to avoid filling up the call stack and 
because it might make certain of the algorithm’s properties clearer. Luckily, to simulate recursive traversal, all we need 
to do is use a stack rather than a set in an algorithm quite like walk in Listing 5-1. Listing 5-5 shows this iterative DFS.