def Dfs(s): #递归版本 global graph,is_Visited is_Visited[s]=1 print(s,end=' ') for each in graph[s]: if is_Visited[each]==False: Dfs(each) def Iter_Dfs(s): #迭代版本 global graph,is_Visited stack=[s] #用栈记录结点 is_Visited[s]=True print(s,end=' ') while stack != []: flag=1 #测试是否应该回溯 for each in graph[s]: if is_Visited[each]==False: s=each stack.append(s) print(s,end=' ') is_Visited[s]=True flag=0 if flag==1: s=stack.pop() #test graph={'A':['B','C'], 'B':['A','C','D'], 'C':['A','B','D','F'], 'D':['B','C'], 'E':['F'], 'F':['C','E']} is_Visited={'A':False,'B':False,'C':False,'D':False,'E':False,'F':False} print("递归版本") Dfs('A') is_Visited={'A':False,'B':False,'C':False,'D':False,'E':False,'F':False} print("\n迭代版本") Iter_Dfs('A')
测试用图与广度优先搜索用的图相同