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')
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question
