如何通过Python代码实例实现基于BFS和DFS的模拟？

本文共计558个文字，预计阅读时间需要3分钟。

BFS算法是一种用于图和树遍历的算法，它按照广度优先的原则，从源节点开始，逐层探索所有可达节点。BFS算法通常使用队列来实现，具体步骤如下：

1. 初始化：创建一个队列和一个集合，分别用于存储待访问的节点和已访问过的节点。

2.将源节点入队，并将源节点加入已访问集合。

3.当队列为空时，算法结束。

4.从队列中取出一个节点，并将其所有未访问过的邻接节点加入队列和已访问集合。

5.重复步骤4，直到队列为空。

BFS算法的优点是能够找到最短路径，并且在无权图中，BFS总是能够找到最短路径。其缺点是对于稠密图，BFS的空间复杂度较高，因为它需要存储所有已访问过的节点。

BFS

""" # @Time : 2020/11/8 # @Author : Jimou Chen """ # 广搜 def bfs(graph, start): queue = [start] # 先把起点入队列 visited = set() # 访问国的点加入 visited.add(start) while len(queue): vertex = queue.pop(0) # 找到队列首元素的连接点 for v in graph[vertex]: if v not in visited: 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')

A B D I F C H E G
Process finished with exit code 0

DFS

""" # @Time : 2020/11/8 # @Author : Jimou Chen """ # 深搜 def dfs(graph, start): stack = [start] visited = set() visited.add(start) while len(stack): vertex = stack.pop() # 找到栈顶元素 for v in graph[vertex]: if v not in visited: 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')

E H G F B A I D C
Process finished with exit code 0

总结

很明显一个用了队列，一个用了栈

利用python语言优势，只需改动pop即可

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持易盾网络。