ActiveState Code

Recipe 576946: Depth first search generator

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 
 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))

Discussion

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)

Comments

  1. 1. At 8:36 a.m. on 3 nov 2009, Matteo Dell'Amico said:

    See also the bfs and dfs implementations I posted in the comments at http://code.activestate.com/recipes/576675/ .

Sign in to comment