Welcome, guest | Sign In | My Account | Store | Cart

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
 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[0]))) == len (G.vertices)

2 comments

Matteo Dell'Amico 12 years, 1 month ago  # | flag

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

BENNY KHOO 8 years, 4 months ago  # | flag

How do I trace the depth level using this function? Thx

Created by Paul W. Miller on Tue, 3 Nov 2009 (MIT)
Python recipes (4591)
Paul W. Miller's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks