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

2024年 1月 23日 92.0k 0

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

BFS算法的工作原理图解

以具有5个节点的无向图为例,如下图:

BFS算法概念原理详细图解 Python代码实现BFS算法

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

BFS算法概念原理详细图解 Python代码实现BFS算法

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

BFS算法概念原理详细图解 Python代码实现BFS算法

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

BFS算法概念原理详细图解 Python代码实现BFS算法

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

BFS算法概念原理详细图解 Python代码实现BFS算法

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

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 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算法的详细内容,更多请关注每日运维网(www.mryunwei.com)其它相关文章!

相关文章

JavaScript2024新功能:Object.groupBy、正则表达式v标志
PHP trim 函数对多字节字符的使用和限制
新函数 json_validate() 、randomizer 类扩展…20 个PHP 8.3 新特性全面解析
使用HTMX为WordPress增效:如何在不使用复杂框架的情况下增强平台功能
为React 19做准备:WordPress 6.6用户指南
如何删除WordPress中的所有评论

发布评论