基于python模拟bfs和dfs代码实例
BFS
""" #@Time:2020/11/8 #@Author:JimouChen """ #广搜 defbfs(graph,start): queue=[start]#先把起点入队列 visited=set()#访问国的点加入 visited.add(start) whilelen(queue): vertex=queue.pop(0) #找到队列首元素的连接点 forvingraph[vertex]: ifvnotinvisited: queue.append(v) visited.add(v) #打印弹出队列的该头元素 print(vertex,end='') if__name__=='__main__': graph={ 'A':['B','D','I'], 'B':['A','F'], 'C':['D','E','I'], 'D':['A','C','F'], 'E':['C','H'], 'F':['B','H'], 'G':['C','H'], 'H':['E','F','G'], 'I':['A','C'] } bfs(graph,'A')
ABDIFCHEG
Processfinishedwithexitcode0
DFS
""" #@Time:2020/11/8 #@Author:JimouChen """ #深搜 defdfs(graph,start): stack=[start] visited=set() visited.add(start) whilelen(stack): vertex=stack.pop()#找到栈顶元素 forvingraph[vertex]: ifvnotinvisited: stack.append(v) visited.add(v) print(vertex,end='') if__name__=='__main__': graph={ 'A':['B','D','I'], 'B':['A','F'], 'C':['D','E','I'], 'D':['A','C','F'], 'E':['C','H'], 'F':['B','H'], 'G':['C','H'], 'H':['E','F','G'], 'I':['A','C'] } dfs(graph,'E')
EHGFBAIDC
Processfinishedwithexitcode0
总结
很明显一个用了队列,一个用了栈
利用python语言优势,只需改动pop即可
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。