DFS和BFS Python3代码对比
通过dic建立邻接图
graph = {
'A': ['B', 'C'],
'B': ['A', 'C', 'D'],
'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'],
'E': ['C', 'D'],
'F': ['D']
}
BFS广度优先算法
def BFS(graph, node):
queue = []#BFS使用栈实现先进先出
queue.append(node)
searched = set()
searched.add(node)
while(len(queue) > 0):
vertex = queue.pop(0)
nodes = graph[vertex]
for node in nodes:
if node not in searched:
queue.append(node)
searched.add(node)
print(vertex)
DFS深度优先算法
def DFS(graph, node):
stack = []#DFS使用栈实现先进后出
stack.append(node)
searched = set()
searched.add(node)
while(len(stack) > 0):
vertex = stack.pop()
nodes = graph[vertex]
for node in nodes:
if node not in searched:
stack.append(node)
searched.add(node)
print(vertex)
总结
- DFS和BFS的区别仅仅在于BFS使用了先进先出的队列(queue)，而DFS使用了先进后出的栈(stack)
- BFS按层推进，从图的一个未遍历的节点出发，先遍历这个节点的相邻节点，再依次遍历每个相邻节点的相邻节点。
- DFS沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底...，不断递归重复此过程，直到所有的顶点都遍历完成
参考：
