转载。 https://blog.csdn.net/m0_37316917/article/details/70879977
广度优先搜索的概念
广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点v，然后由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3….wn，然后再依次访问w1，w2,…,wi的所有未被访问过的邻接顶点，再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点….以此类推，直到途中所有的顶点都被访问过为止。类似的想法还将应用与Dijkstra单源最短路径算法和Prim最小生成树算法。（这个过程我觉得可以举个这样的例子来理解：比如要从你开始介绍你的家人，可以先从你开始，然后一个一个介绍和你有直接血缘关系的这一层亲属（爸爸妈妈儿子女儿），当把你所有的这些第一层亲属全都遍历完之后再从你的妈妈开始遍历（也可以从爸爸或儿子），把你妈妈的有直接血缘关系的亲戚先遍历一遍，然后再从爸爸开始，以此类推，直到全部都遍历完成）。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有回退的情况（另一篇博客会介绍），因此它不是一个递归的算法，为了实现逐层的访问，算法必须借助一个辅助队列并且以非递归的形式来实现。算法伪代码
其伪代码如下：
bool visited[MAX_VERTEX_NUM];//访问数组，也就是顶点个数void BFSTraverse(Graph G)//外层的函数，为准备实现遍历做一些准备工作。{ for（int i=0;i =0;w=NextNeighbor(G,v,w))//这一步是检查v的所有邻接顶点 if(!visited[w]){ visit(w); visited[w]=true; EnQueue(Q,w); //如果w没有被访问过，那么访问这个顶点，并把它入队 }} 实例以及解析
BFS算法性能分析
无论是邻接表还是邻接矩阵的存储访问，BFS算法都需要借助一个辅助队列Q，n个顶点都需要入队依次，在最坏的情况下，空间复杂度为O（|V|）。
当采用邻接表存储方式时，每个顶点均需要搜索依次（或入队依次），故时间复杂度为O（|V|），再搜索任一顶点时，每条边至少访问依次，故时间复杂度为O(|E|)，算法的总时间复杂度为O(|V|+|E|)；当采用邻接矩阵存储方式的时候，查找每个顶点的邻接点所需时间为O（|V|），故算法总的时间复杂度为O(|V|²)。BFS算法求单源最短路径问题
如果图G=（V，E）为非带权图。定义从顶点u到顶点v的最短路径d（u，v）为从u到v的任何路径中最少的边数；如果从u到v没有通路，则d（u，v）=∞。
使用BFS，我们可以求解一个满足上述定义的非带权图的单源最短路径问题，这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的（这让我想到：在2d游戏中计算两个位置的最短路径是否可以采用BFS算法来求出呢？） BFS算法求解单源最短路径问题的算法如下：void BFS_MIN_Distance(Graph G,int u){//d[i]表示从u到i结点的最短路径 for(i=0;i =0;w=NextNeighbor(G,u,w)) if(!visited[w]){ //w为u未曾访问的邻接顶点 visited[w]=true;//设为已经访问 d[w]=d[u]+1;//路径长度+1 EnQueque(Q,w);//w顶点入队 } }}