Source code online books for professionals by professionals

Listing 5-8.  Topological Sorting Based on Depth-First Search
def dfs_topsort(G):
    S, res = set(), []                          # History and result
    def recurse(u):                             # Traversal subroutine
        if u in S: return                       # Ignore visited nodes
        S.add(u)                                # Otherwise: Add to history
        for v in G[u]:
            recurse(v)                          # Recurse through neighbors
        res.append(u)                           # Finished with u: Append it
13
The dfs_topsort function can also be used to sort the nodes of a general graph by decreasing finish times, as needed when 
looking for strongly connected components, discussed later in this chapter.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
105
    for u in G:
        recurse(u)                              # Cover entire graph
    res.reverse()                               # It's all backward so far
    return res
 
There are a few things that are worth noting in this new topological sorting algorithm. For one thing, I’m explicitly 
including a for loop over all the nodes to make sure the entire graph is traversed. (Exercise 5-8 asks you to show 
that this will work.) The check for whether a node is already in the history set (S) is now placed right inside recurse, 
so we don’t need to put it in both of the for loops. Also, because recurse is an internal function, with access to the 
surrounding scope (in particular, S and res), the only parameter needed is the node we’re traversing from. Finally, 
remember that we want the nodes to be sorted in reverse, based on their finish times. That’s why the res list is 
reversed before it’s returned.
This topsort performs some processing on each node as it backtracks over them (it appends them to the result 
list). The order in which DFS backtracks over nodes (that is, the order of their finish times) is called postorder, while 
the order in which it visits them in the first place is called preorder. Processing at these times is called preorder or 
postorder processing. (Exercise 5-9 asks you to add general hooks for this sort of processing in DFS.)