广度优先搜索（BFS）算法详解
广度优先搜索（BreadthFirstSearch）简称广搜或者BFS，是遍历图存储结构的一种算法，既适用于无向图（网），也适用于有向图（网）。所谓图的遍历，简单理解就是逐个访问图中的顶点，确保每个顶点都只访问一次。
首先通过一个样例，给大家讲解广度优先搜索算法是如何实现图的遍历的。图1广度优先搜索算法遍历图使用广度优先搜索算法，遍历图1中无向图的过程是：1)初始状态下，图中所有顶点都是尚未访问的，因此任选一个顶点出发，开始遍历整张图。比如从V1顶点出发，先访问V1：图2访问顶点V12)从V1出发，可以找到V2和V3，它们都没有被访问，所以访问它们：图3访问V2和V3注意：本图中先访问的是V2，也可以先访问V3。当可以访问的顶点有多个时，访问的顺序是不唯一的，可以根据找到各个顶点的先后次序依次访问它们。后续过程也会遇到类似情况，不再重复赘述。
3)根据图3中的顶点访问顺序，紧邻V1的顶点已经访问过，接下来访问紧邻V2的顶点。从V2顶点出发，可以找到V1、V4和V5，尚未访问的有V4和V5，因此访问它们：图4访问V4和V54) 根据图4中的顶点访问顺序，接下来访问紧邻V3的顶点。从V3顶点出发，可以找到V1、V6和V7，尚未访问的有V6和V7，因此访问它们：图5访问V6和V75)根据图5中的顶点访问顺序，接下来访问紧邻V4的顶点。从V4顶点出发，可以找到V2和V8，只有V8尚未访问，因此访问它：图6访问V86)根据图6的顶点访问顺序，接下来访问紧邻V5的顶点。观察图6中的无向图不难发现，与V5紧邻的V2和V8都已经访问过，无法再找到尚未访问的顶点。此时，广度优先搜索算法会直接跳过V5，继续从其它的顶点出发。7)广度优先搜索算法先后从V6、V7、V8出发，寻找和它们紧邻、尚未访问的顶点，但寻找的结果都和V5一样，找不到符合要求的顶点。8)自V8之后，访问序列中再无其它顶点，意味着从V1顶点出发，无法再找到尚未访问的顶点。这种情况下，广度优先搜索算法会从图的所有顶点中重新选择一个尚未访问的顶点，然后从此顶点出发，以同样的思路继续寻找其它尚未访问的顶点。本例中的无向图是一个连通图，从V1出发可以找到所有的顶点，因此广度优先搜索算法继V1顶点之后无法再找到新的尚未访问的顶点，算法执行结束。对于连通图来说，广度优先搜索算法从一个顶点出发就能访问图中所有的顶点。但是对于非连通图来说，广度优先搜索算法必须从各个连通分量中选择一个顶点出发，才能访问到所有的顶点。
广度优先搜索算法的具体实现所谓广度优先搜索，就是从图中的某个顶点出发，寻找紧邻的、尚未访问的顶点，找到多少就访问多少，然后分别从找到的这些顶点出发，继续寻找紧邻的、尚未访问的顶点。当从某个顶点出发，所有和它连通的顶点都访问完之后，广度优先搜索算法会重新选择一个尚未访问的顶点（非连通图中就存在这样的顶点），继续以同样的思路寻找未访问的其它顶点。直到图中所有顶点都被访问，广度优先搜索算法才会结束执行。图的存储结构有很多种，大体上可以分为顺序存储和链式存储（又细分为邻接表结构、十字链表结构和邻接多重表结构），各个存储结构有自己的特点。选用不同的存储结构，广度优先搜索算法的具体实现不同，但算法的思想是不变的。这里以图的顺序存储结构为例，广度优先搜索算法的C语言实现代码如下：#include#include#defineMAX_VERtEX_NUM20//顶点的最大数量#defineVRTypeint//表示顶点之间关系的数据类型#defineVertexTypeint//顶点的数据类型typedefenum{false,true}bool;//定义bool型常量boolvisited[MAX_VERtEX_NUM];//设置全局数组，记录每个顶点是否被访问过//队列链表中的结点类型typedefstructQueue{VertexTypedata;structQueue*next;}Queue;typedefstruct{VRTypeadj;//用0表示不相邻，用1表示相邻}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedefstruct{VertexTypevexs[MAX_VERtEX_NUM];//存储图中的顶点AdjMatrixarcs;//二维数组，记录顶点之间的关系intvexnum,arcnum;//记录图的顶点数和弧（边）数}MGraph;//判断v顶点在二维数组中的位置intLocateVex(MGraph*G,VertexTypev){inti;//遍历一维数组，找到变量vfor(i=0;ivexnum;i++){if(G->vexs[i]==v){break;}}//如果找不到，输出提示语句，返回-1if(i>G->vexnum){printf("nothisvertex ");return-1;}returni;}//构造无向图voidCreateDN(MGraph*G){inti,j,n,m;intv1,v2;scanf("%d,%d",&(G->vexnum),&(G->arcnum));for(i=0;ivexnum;i++){scanf("%d",&(G->vexs[i]));}for(i=0;ivexnum;i++){for(j=0;jvexnum;j++){G->arcs[i][j].adj=0;}}for(i=0;iarcnum;i++){scanf("%d,%d",&v1,&v2);n=LocateVex(G,v1);m=LocateVex(G,v2);if(m==-1||n==-1){printf("nothisvertex ");return;}G->arcs[n][m].adj=1;G->arcs[m][n].adj=1;}}intFirstAdjVex(MGraphG,intv){inti;//对于数组下标v处的顶点，找到第一个和它相邻的顶点，并返回该顶点的数组下标for(i=0;idata=v;element->next=NULL;//将v添加到队列链表的尾部while(temp->next!=NULL){temp=temp->next;}temp->next=element;}//队头元素出队列voidDeQueue(Queue**Q,int*u){Queue*del=(*Q)->next;(*u)=(*Q)->next->data;(*Q)->next=(*Q)->next->next;free(del);}//判断队列是否为空boolQueueEmpty(Queue*Q){if(Q->next==NULL){returntrue;}returnfalse;}//释放队列占用的堆空间voidDelQueue(Queue*Q){Queue*del=NULL;while(Q->next){del=Q->next;Q->next=Q->next->next;free(del);}free(Q);}//广度优先搜索voidBFSTraverse(MGraphG){intv,u,w;Queue*Q=NULL;InitQueue(&Q);//将用做标记的visit数组初始化为falsefor(v=0;vvertice[pos].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0)//判断是否遍历过 { queue[tail]=p->adjvex;//入队操作 visited[p->adjvex]=1;//标记遍历过 tail++; } p=p->next; } }}5. 应用BFS算法的实际应用场景，最典型的有地图搜索，迷宫寻路等，需要有“状态”以及状态改变场景的搜索算法，同时BFS由于不需要像DFS算法那样回溯，故比DFS效率可能会更高一些。基于BFS算法的该进算法，比如说R星寻路，DBFS(双向广搜)算法等这类改进算法场景被应用在实际游戏设计，GPS导航设计等场景中。
广度优先搜索
算法简介：广度优先搜索问题给定一个一幅图和一个起点s，回答“从s到给定的顶点v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）。“
思路边数最少，很自然想到从从经过1条边能到达的节点有哪些？然后经过这些边再到达的节点有哪些？这样我不就能够想出来最短的路径了吗？没错，这是非常简单的想法，然而真正的广度优先算法也是这样，简单而有效。
解决方法图片来源：https://commons.wikimedia.org/w/index.php?curid=1547848
上面这幅图我要找到从1到12的最短路径，则我会从1经过1条边可以到达的节点（234）搜索，发现没有，接下来搜索节点（234）通过1条边能够到达的顶点（5678），发现没有，接下来搜索节点（5678），发现没有，接下来搜索节点（5678）通过1条边能够到达的节点（9101112），搜索到最后一个，发现搜索到了。如果你每次经过一条边则记录加1，则现在经过了三条边，即最短路径是3条边，
实现方案当已经理解了算法思想，接下来就应该实现了。最重要的一步是思考使用什么样的数据结构，想想这里的搜索一个集合，那自然就是遍历他们，接下来还要遍历他们通过一条边能够到达节点，普通的想法是先判断他们，如果没有，则再遍历他们，然后生成的所有节点再加入一个新的集合当中。
问题：发现了没，这里遍历了两遍集合。还有就是新的节点加入一个新的集合，每次都要声明新的数组吗？这是有多麻烦。
解决方案：这里遍历了两遍，其实我先生成新的节点和后生成新的节点只是多占用一点空间而已，我要是在遍历第一个节点如果判断不是就直接生成新的节点也可以，这样就不用遍历第二遍了，加入新的集合解决起来有点棘手，如果我可以仍然放在集合里面继续遍历就好了，对！就是这样，所以在集合里会有顺序的关系，不能我先遍历第一个节点，接着直接遍历新的节点，所以说我们的数据就要有顺序之分，所以想想有什么样的数据存储方式能够有顺序，常见的数组就够了，如果稍微学过数据结构，链表也可以。
编程的思路：遍历数组，从第一个节点开始，如果不是，则生成新节点加入到数组的最后一个节点后面，所以如果是c语言，一定要将数组声明大一些。然后不断遍历即可，直到找到。
八数码实现问题八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。
思路移动棋子最少，当然是使用广度优先搜索来解决。所以这里的每个节点就要是一个3*3的矩阵。如果在c语言中，可以使用结构体。
structnode{intxy[3][3];};实现方案空白棋子用0代替接受初始节点的信息和目标节点的信息找到空白棋子很简单，直接遍历就好，但是如何返回它的x和y坐标，试着能不能使用一个数字代替，后来发现确实可以。intloction(intnum){inti;for(i=0;i