深入解析BFS算法原理，带图解说明，并附带Python代码实现BFS算法

百变鹏仔 23小时前 #Python

文章标签算法

bfs又名广度优先搜索，和dfs算法一样都是递归算法，不同的是，bfs算法通过队列，在避免循环的同时遍历目标所有节点。

BFS算法的工作原理图解

以具有5个节点的无向图为例，如下图：

从节点0开始，BFS算法首先将其放入Visited列表并将其所有相邻节点放入队列。

立即学习“Python免费学习笔记（深入）”；

接下来，访问队列前面的节点1，并转到节点1相邻的节点。因为节点0已经被访问过，所以访问节点2。

节点2有一个未访问的相邻节点4，但因为节点4在队列的最后，因此我们要先访问位于队列前面的节点3。

队列中只剩下节点4没有被访问，所以最后访问节点4。

至此，已经完成了此无向图的广度优先遍历。

BFS算法的伪代码

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

Python代码实现BFS算法

import collectionsdef 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算法

BFS算法的工作原理图解

BFS算法的伪代码

Python代码实现BFS算法

Python脚本自动刷新Excel电子表格

了解Python编程行业中最适合自己的就业选择

Python中的map函数有什么用途？

企业招聘Python开发者的常见要求

如何使用Python生成两个日期之间的k个随机日期？