本文主要是介绍广度优先搜索Breadth-First-Search，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
1.问题
2.算法
3.代码
4.参考文献
1.问题
广度优先搜索，稍微学过算法的人都知道，网上也一大堆资料，这里就不做过多介绍了。直接看问题，还是从下图招到一条从城市Arad到Bucharest的路径。
该图是连通图，所以必然存在一条路径，只是如何找到最短路径。
2.算法
还是贴一个算法的伪代码吧：
1 procedure BFS(G, root) is2 let Q be a queue3 label root as explored4 Q.enqueue(root)5 while Q is not empty do6 v := Q.dequeue()7 if v is the goal then8 return v9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as explored then
11 label w as explored
12 w.parent := v
13 Q.enqueue(w)算法实现也可以用递归版本，不过用递归在树的深度比较大时不如使用队列高效。
广度优先搜索总是能找到一个动作最少的解，因为当他生成深度为d的节点时，说明已经生成了升读为d-1的所有节点，如果其中一个节点是解，它应该已经被找到了，这对于所有动作都具有相同代价的问题，它是代价最优的，但对于不具有该特性的问题，则不一定是最优的。这两种情况都是完备的。想象我们在搜索一棵均衡树，每个节点均有b个子节点，则当遍历了d层之后，生成的节点总数为：
所有节点都存储在内存中，所以时间和空间复杂度都是 ，这样的指数级上界是可怕的，举个例子：假设
,假设计算机可以每秒处理100w个节点，每个节点需要1Kb存储空间，那么该算法可以再3小时完成计算，但是需要10TB的内存。因此，对于广度优先搜索，内存是一个比执行时间更严重的问题。
3.代码
广度优先搜索和最佳优先搜索很像，我在最佳优先搜索中也提到过，这里不在贴重复的代码了，直接贴广度优先搜索：
# -*- coding: utf-8 -*-
"""
Created on Thu Sep 5 18:14:14 2024@author: Paul
"""from collections import deque
from citydata import dist_mat,Nodesdef BFS(mat,start,end):q=deque() #使用标准库中的优先队列visited=[start]q.append(start)while q:curr=q.popleft()print(curr)for city,_ in mat[Nodes.index(curr)]: # _代表这里不使用距离信息child=Nodes[city]if child==end:return Trueif child not in visited:q.append(child)visited.append(child)return False从上面的代码可以看出，我这里没有使用深度信息，而是直接安层次顺序访问，也就是前面提到的，每个城市到另一个城市的代价一样，最后可以得到代价最低的访问层次路径：
Node('Arad')
Node('Zerind')
Node('Sibiu')
Node('Timisoara')
Node('Oradea')
Node('Fagaras')
也就是：
其中Siubiu在第一层就访问过，所以第三层就不会再访问一次（因此打了一个×）
我们在第三层就访问到了目的地，也就是至少需要三条路径才能访问到。
问题来了，我们这次还是没确定从起点到目标点的最短路径，因为没有用到距离信息，别急，下一节DijkStra算法来帮我们彻底解决这个问题。
4.参考文献
1. 《人工智能：一种现代的方法（第4版）》第三章：无信息搜索策略
这篇关于广度优先搜索Breadth-First-Search的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
