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

Very simple depth first search and breath first graph traversal. This is based on the find_path written by Guido van Rossum.

Python, 39 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def recursive_dfs(graph, start, path=[]):
  '''recursive depth first search from start'''
  path=path+[start]
  for node in graph[start]:
    if not node in path:
      path=recursive_dfs(graph, node, path)
  return path

def iterative_dfs(graph, start, path=[]):
  '''iterative depth first search from start'''
  q=[start]
  while q:
    v=q.pop(0)
    if v not in path:
      path=path+[v]
      q=graph[v]+q
  return path

def iterative_bfs(graph, start, path=[]):
  '''iterative breadth first search from start'''
  q=[start]
  while q:
    v=q.pop(0)
    if not v in path:
      path=path+[v]
      q=q+graph[v]
  return path

'''
   +---- A
   |   /   \
   |  B--D--C
   |   \ | /
   +---- E
'''
graph = {'A':['B','C'],'B':['D','E'],'C':['D','E'],'D':['E'],'E':['A']}
print 'recursive dfs ', recursive_dfs(graph, 'A')
print 'iterative dfs ', iterative_dfs(graph, 'A')
print 'iterative bfs ', iterative_bfs(graph, 'A')

I have tried downloading quite a few python programs. Often, they don't run because of missing modules on my system, they crash because of bad data or they are too complex to understand.

A while ago, I read a graph implementation by Guido van Rossen that was deceptively simple. Now, I insist on a pure python minimal system with the least complexity. The idea is to be able to explore the algorithm. Later, you can refine and optimize the code but you will probably want to do this in a compiled language.

The routines are traversals that Guido did not include.

4 comments

Matteo Dell'Amico 14 years, 11 months ago  # | flag

For an iterative version of bfs and dfs implemented with generators, see the one I posted at http://code.activestate.com/recipes/576675/.

Matteo Dell'Amico 14 years, 11 months ago  # | flag

Addendum: look for it in the comments.

bruce wernick (author) 14 years, 11 months ago  # | flag

Thanks, I didn't see this one. In my case, the intention was to keep the code as simple as possible and to use the same structure as in the Van Rossen article. So, the queue and the path are both simple python lists. It is surely not the most efficient but it is very transparent, especially for the beginner to experiment with graphs.

My problem with previous downloads is that some use Scipy and Numpy and after many attempts, I can still not get these to run. There is always a module missing or a version mismatch. Really frustrating. I would prefer to see the numerical methods in pure python only.

arvindh sanu 7 years, 11 months ago  # | flag

def iterative_bfs(graph, start): '''iterative breadth first search from start''' bfs_tree = {start: {"parents":[], "children":[], "level":0}} q = [start] while q: current = q.pop(0) for v in graph[current]: if not v in bfs_tree: bfs_tree[v]={"parents":[current], "children":[], "level": bfs_tree[current]["level"] + 1} bfs_tree[current]["children"].append(v) q.append(v) else: if bfs_tree[v]["level"] > bfs_tree[current]["level"]: bfs_tree[current]["children"].append(v) bfs_tree[v]["parents"].append(current)

Use this for BFS and for travesing

Created by bruce wernick on Wed, 22 Apr 2009 (MIT)
Python recipes (4591)
bruce wernick's recipes (1)

Required Modules

  • (none specified)

Other Information and Tasks