Source code online books for professionals by professionals

Listing 5-6.  A General Graph Traversal Function
def traverse(G, s, qtype=set):
    S, Q = set(), qtype()
    Q.add(s)
    while Q:
        u = Q.pop()
        if u in S: continue
        S.add(u)
        for v in G[u]:
            Q.add(v)
        yield u
 
The default queue type here is set, making it similar to the original (arbitrary) walk. You could easily define a 
stack type (with the proper add and pop methods of our general queue protocol), perhaps like this:
 
class stack(list):
    add = list.append
 
The previous depth-first test could then be repeated as follows:
 
>>> list(traverse(G, 0, stack))
[0, 5, 7, 6, 2, 3, 4, 1]
 
Of course, it’s also quite OK to implement special-purpose versions of the various traversal algorithms, even 
though they can be expressed in much the same form.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
104
Depth-First Timestamps and Topological Sorting (Again)
As mentioned earlier, remembering and avoiding previously visited nodes is what keeps us from going in circles  
(or, rather, cycles), and a traversal without cycles naturally forms a tree. Such traversal trees have different names 
based on how they were constructed; for DFS, they are aptly named depth-first trees (or DFS trees). As with any 
traversal tree, the structure of a DFS tree is determined by the order in which the nodes are visited. The thing that is