This is the standard iterative DFS code modified to yield the vertices visited, so you don't have to pass a function into the DFS routine to process them. Note that this code is not quite complete... you'll need to define the function neighbors (v) based on your graph representation.
1 2 3 4 5 6 7 8 9 10
def DFS (G, v): yield v visited = set ([v]) S = neighbors (v) while S: w = S.pop() if w not in visited: yield w visited.add (w) S.extend (neighbors (w))
To use this code, just do:
for v in DFS (G, start): process (v)
Personally, I think this is more natural than passing a function into a DFS routine.
A nice example application is the following function to tell whether the graph G is connected or not:
def is_connected (G): return len (list (DFS (G, G.vertices))) == len (G.vertices)
See also the bfs and dfs implementations I posted in the comments at http://code.activestate.com/recipes/576675/ .
How do I trace the depth level using this function? Thx