Python DFS and BFS

Question

Here http://www.python.org/doc/essays/graphs/ - is this DFS right?

I'm trying to do something with the "brothers," but that won't work. Can anyone write BFS similar to the code from this site.

Answer 1

Yes, this is DFS.

To write BFS, you just need to save the "todo" queue. You probably also want to include the function in the generator, because often BFS intentionally ends before it generates all possible paths. Thus, this function can be used to search for path_path or find_all_paths.

def paths(graph, start, end): todo = [[start, [start]]] while 0 < len(todo): (node, path) = todo.pop(0) for next_node in graph[node]: if next_node in path: continue elif next_node == end: yield path + [next_node] else: todo.append([next_node, path + [next_node]]) 

And an example of how to use it:

 graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F'], 'F': ['C']} for path in paths(graph, 'A', 'D'): print path 

Answer 2

Why don't you check out a decent graph implementation like python-graph?

http://code.google.com/p/python-graph/

Answer 3

Here O (N * max (vertex degree)) is the width search implementation. The bfs function generates nodes in the first order and for each generator, which can be used to track the shortest path to the starting point. The lazy nature of the paths means that you can iterate through the generated node to find the objects you are interested in without paying the cost of creating all the intermediate paths.

 import collections GRAPH = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F'], 'F': ['C']} def build_path(node, previous_map): while node: yield node node = previous_map.get(node) def bfs(start, graph): previous_map = {} todo = collections.deque() todo.append(start) while todo: node = todo.popleft() yield node, build_path(node, previous) for next_node in graph.get(node, []): if next_node not in previous_map: previous_map[next_node] = node todo.append(next_node) for node, path in bfs('A', GRAPH): print node, list(path) 

Answer 4

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