bfs又名广度优先搜索，和dfs算法一样都是递归算法，不同的是，bfs算法通过队列，在避免循环的同时遍历目标所有节点。
以具有5个节点的无向图为例，如下图：
从节点0开始，BFS算法首先将其放入Visited列表并将其所有相邻节点放入队列。
立即学习“Python免费学习笔记（深入）”；
接下来，访问队列前面的节点1，并转到节点1相邻的节点。因为节点0已经被访问过，所以访问节点2。
节点2有一个未访问的相邻节点4，但因为节点4在队列的最后，因此我们要先访问位于队列前面的节点3。
队列中只剩下节点4没有被访问，所以最后访问节点4。
至此，已经完成了此无向图的广度优先遍历。
create a queue Q mark v as visited and put v into Q while Q is non-empty remove the head u of Q mark and enqueue all (unvisited) neighbours of u
import collections
def bfs(graph, root):
visited, queue = set(), collections.deque([root])
visited.add(root)
while queue:
vertex = queue.popleft()
print(str(vertex) + " ", end="")
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)以上就是深入解析BFS算法原理，带图解说明，并附带Python代码实现BFS算法的详细内容，更多请关注php中文网其它相关文章！
python怎么学习？python怎么入门？python在哪学？python怎么学才快？不用担心，这里为大家提供了python速学教程(入门到精通)，有需要的小伙伴保存下载就能学习啦！
广告![ThinkPHP5快速开发企业站点[全程实录]](https://img.php.cn/upload/course/000/000/068/6253d918a3ce7278.png)
收藏
收藏
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
484
