?简介
? ? ? ? 广度优先搜索（Breadth First Search）又名宽度优先搜索，是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
? ? ? ? ? ? ? 图1 ? ? ? ?广度优先搜索?
??????? 广度优先搜索适合找最优解，如图1所示：1就是从0到1；2就是从0到2；5就是从0到2到5……??
????????进行广度优先搜索需要用到队列，因为广度优先搜索需要保证先访问节点的未访问临接点，恰好是先进先出。
????????已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。
????????之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和未找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+l的其他顶点。
????????为了保持搜索的轨迹，宽度优先搜索为每个顶点着色：白色、灰色或黑色。算法开始前所有顶点都是白色，随着搜索的进行，各顶点会逐渐变成灰色，然后成为黑色。在搜索中第一次碰到一顶点时，我们说该顶点被发现，此时该顶点变为非白色顶点。因此，灰色和黑色顶点都已被发现，但是，宽度优先搜索算法对它们加以区分以保证搜索以宽度优先的方式执行。若(u,v)∈E且顶点u为黑色，那么顶点v要么是灰色，要么是黑色，就是说，所有和黑色顶点邻接的顶点都已被发现。灰色顶点可以与一些白色顶点相邻接，它们代表着已找到和未找到顶点之间的边界。
????????在宽度优先搜索过程中建立了一棵宽度优先树，起始时只包含根
节点，即源顶点s.在扫描已发现顶点u的临接表的过程中每发现一个白色顶点v，该顶点v及边(u,v)就被添加到树中。在宽度优先树中，我们称结点u 是结点v的先辈或父母结点。因为一个结点至多只能被发现一次，因此它最多只能有--个父母结点。相对根结点来说祖先和后裔关系的定义和通常一样：如果u处于树中从根s到结点v的路径中，那么u称为v的祖先，v是u的后裔。
流程
?标记起始点；
?从起始点往下搜索取所有一步可达的点，判断它们是否为目标点：
?????●如果找到目标，则结束并回传结果‘
?????●否则将它坐在的点进行标记
?如果所有点全部被标记，表示整张图都检查过了，也就是说途中没有我们想要搜索的目标。结束搜索并回传“找不到目标”
?重复第2步
代码模版
void BFS(int s)
{
queue<int> q;
q.push(s);
while(!q.empty())
{
取出队首元素 top;
访问队首元素 top;
将队首元素出队;
将 top的下一层结点中未曾入队的结点全部入队，并设置为已入队;
}
}