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
Download
Copy to clipboard1 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.
For an iterative version of bfs and dfs implemented with generators, see the one I posted at http://code.activestate.com/recipes/576675/.
Addendum: look for it in the comments.
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.
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