Source code online books for professionals by professionals

Listing 5-5.  Iterative Depth-First Search
def iter_dfs(G, s):
    S, Q = set(), []                            # Visited-set and queue
    Q.append(s)                                 # We plan on visiting s
    while Q:                                    # Planned nodes left?
        u = Q.pop()                             # Get one
        if u in S: continue                     # Already visited? Skip it
        S.add(u)                                # We've visited it now
        Q.extend(G[u])                          # Schedule all neighbors
        yield u                                 # Report u as visited
 
Beyond the use of a stack (a last-in, first-out, or LIFO, queue, in this case implemented by a list, using append and pop), 
there are a couple of tweaks here. For example, in my original walk function, the queue was a set, so we’d never risk 
having the same node scheduled for more than one visit. Once we start using other queue structures, this is no longer 
the case. I’ve solved this by checking a node for membership in S (that is, whether we’ve already visited the node) 
before adding its neighbors.
To make the traversal a bit more useful, I’ve also added a yield statement, which will let you iterate over the 
graph nodes in DFS order. For example, if you had the graph from Figure 2-3 in the variable G, you could try the 
following:
 
>>> list(iter_dfs(G, 0))
[0, 5, 7, 6, 2, 3, 4, 1]
 

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
103
One thing worth noting is that I just ran DFS on a directed graph, while I’ve discussed only how it would work 
on undirected graphs. Actually, both DFS and the other traversal algorithms work just as well for directed graphs. 
However, if you use DFS on a directed graph, you can’t expect it to explore an entire connected component. For 
example, for the graph in Figure 2-3, traversing from any other start node than a would mean that a would never be 
seen because it has no in-edges.
Tip
 
■
  for finding connected components in a directed graph, you can easily construct the underlying undirected graph 
as a first step. or you could simply go through the graph and add all the reverse edges. this can be useful for other 
algorithms as well. sometimes, you may not even construct the undirected graph; simply considering each edge in both 
directions when using the directed graph may be sufficient.
You can think of this in terms of Trémaux’s algorithm as well. You’d still be allowed to traverse each (directed) 
passage both ways, but you’d be allowed to go forward only along the edge direction, and you’d have to backtrack 
against the edge direction.
In fact, the structure of the iter_dfs function is pretty close to how we might implement the general traversal 
algorithm hinted at earlier—one where only the queue need be replaced. Let’s beef up walk to the more mature 
traverse (Listing 5-6).