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.
Python, 10 lines
Download
Copy to clipboard1 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[0]))) == len (G.vertices)
Tags: algorithms, graphs
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