Source code online books for professionals by professionals

Listing 5-7.  Depth-First Search with Timestamps
def dfs(G, s, d, f, S=None, t=0):
    if S is None: S = set()                     # Initialize the history
    d[s] = t; t += 1                            # Set discover time
    S.add(s)                                    # We've visited s
    for u in G[s]:                              # Explore neighbors
        if u in S: continue                     # Already visited. Skip
        t = dfs(G, u, d, f, S, t)               # Recurse; update timestamp
    f[s] = t; t += 1                            # Set finish time
    return t                                    # Return timestamp
 
The parameters d and f should be mappings (dictionaries, for example). The DFS property then states that (1) 
every node is discovered before its descendants in the DFS tree, and (2) every node is finished after its descendants 
in the DFS. This follows rather directly from the recursive formulation of the algorithm, but you could easily do an 
induction proof to convince yourself that it’s true.
One immediate consequence of this property is that we can use DFS for topological sorting, already discussed 
in Chapter 4. If we perform DFS on a DAG, we could simply sort the nodes based on their descending finish times, 
and they’d be topologically sorted. Each node u would then precede all its descendants in the DFS tree, which would 
be any nodes reachable from u, that is, nodes that depend on u. It is in cases like this that it pays to know how an 
algorithm works. Instead of first calling our timestamping DFS and then sorting afterward, we could simply perform 
the topological sorting during a custom DFS, by appending nodes when backtracking, as shown in Listing 5-8.
13