文档介绍：第七讲搜索专题广度优先(BFS)ACM算法与程序设计数学科学学院:汪小平wxiaoping325@淬奇滁颐钞嚏蓉洽债刷蒋摧未阔升变钡硒晦跳星矩榷肝焦缉滨帖趋罪畦***(Breadth-First-Search)也被作宽度优先搜索,或横向优先搜索,简称BFS。BFS是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。(稳扎稳打,步步推进)广度优先搜索的实现一般采用队列。所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。因为所有节点都必须被储存,因此BFS的空间复杂度为O(|V|,其中|V|是节点的数目。另一种说法称BFS的空间复杂度为O(BM),其中B是最大分支系数,而M是树的最长路径长度。由于对空间的大量需求,因此BFS并不适合解非常大的问题。最差情形下,BFS必须寻找所有到可能节点的所有路径,因此其时间复杂度为O(|V|+|E|),其中|V|是节点的数目,而|E|是图中边的数目。,城市间有数条道路相连接。从法兰克福开始执行广度优先搜索算法,所产生的广度优先搜索算法树。、首先将根节点放入队列中。2、从队列中取出第一个节点,并检验它是否为目标。如果找到目标,则结束搜寻并回传结果。否则将它所有尚未检验过的直接子节点加入队列中。3、若队列为空,表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。4、重复步骤2。:voidBFS(VLinkG[],intv){intw;VISIT(v);/*访问顶点v*/visited[v]=1;/*顶点v对应的访问标记置为1*/ADDQ(Q,v);while(!QMPTYQ(Q)){v=DELQ(Q);/*退出队头元素v*/w=FIRSTADJ(G,v);/*求v的第1个邻接点。无邻接点则返回-1*/while(w!=-1){if(visited[w]==0)/*未检验过*/{VISIT(w);/*访问顶点v*/ADDQ(Q,w);/*当前被访问的顶点w进队*/visited[w]=1;/*顶点w对应的访问标记置为1*/}W=NEXTADJ(G,v);/*求v的下一个邻接点。若无邻接点则返回-1*/}}}。可怜的小老鼠被困在了迷宫里面想要逃出去,但是它不知道到底该怎么走,无论如何还是先选定一个方向走一下再说。我们对各个方向设定一个优先级,比如我们设定先向上走,再向右走,然后是向下,向左。这个顺序是顺时针排的。不难相到,通过设定一个优先级,我们可以保证在行进过程不会因为随机选择而出现重复情况。深度优先搜索的思路是找到一条可能的路就一直那么走下去只到走不通为止。这个走不通可能的情况很多,也许是遇到了自然的障碍物,也就是到了死胡同走不下去了,这个时侯只有倒退回去。但是现实总是充满了陷阱。或许就存在这么一种路,当你辛辛苦苦走了几十步甚至上百步之后才发现那是一个没有未来的选择。我们可以在迷宫中给老鼠设定,上帝也可以在人生里为我们设定。。该怎么办才能防止这种情况的发生呢?对,我们可以叫住他!“喂,那条路不能走了,快回来!”实现起来其实很简单,就是在程序里面加一个深度判断,如果深度达到了一个上界,我们就不继续往下走了,也就是跳出返回。其实这里面要涉及的还有很多,比如迭代加深搜索,A*等。其实我们可以让那只老鼠变得聪明一点的。假如我们的主角不是一只小老鼠,而是一大群,如果你是老鼠王,你会怎么安排让你的子民们尽快逃生?Thinking。。。,让老鼠们分头行动。我们给每一只老鼠都配一个对讲机。从出发点开始分成四个小队,四个小队分别分别负责四个方向,一起出发。每次只能选择没有去过的地方走,没有去过既包括自己没有去过也要包括别的老鼠没有去过,这个我们可以用一个布尔数组在去过的地方标记一下,对于小老鼠来说标记的方式可能会比较特殊。每次到一个位置都可能会有几种不同的走法,那好,我们把当前的这个小队再次划分,每个能走的方向都派一个小小队去。如果没有路可走了