（贵州省普通高中信息学奥赛CSP-JS NOIP—提高组C++知识点讲解）第10讲 深度优先广度优先

学科竞赛编程 C++ NOIP NOI IOI 1 深度优先搜索  深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。 深度优先遍历图的方法是，从图中某顶点v出发： （1）访问顶点v； （2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问； （3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。当然，当人们刚刚掌握深度优先搜索的时候常常用它来走迷宫. bool visited[MaxVnum]; void DFS(Graph G,int v) { visited[v]= true; //从V开始访问，flag它 printf("%d",v); //打印出V for(int j=0;j<G.vexnum;j++) if(G.arcs[v][j]==1&&visited[j]== false) //这里可以获得V未访问过的邻接点 DFS(G,j); //递归调用，如果所有节点都被访问过，就回溯，而不再调用这里的DFS } void DFSTraverse(Graph G) { for (int v = 0; v < G.vexnum; v++) visited[v] = false; //刚开始都没有被访问过 for (int v = 0; v < G.vexnum; ++v) if (visited[v] == false) //从没有访问过的第一个元素来遍历图 DFS(G, v); } 广度优先搜索 广度优先搜索算法（又称宽度优先搜索），简称BFS。BFS每次都先将搜索树每一层的所有节点全部访问完毕后再访问下一层，因此也被称作“按层搜索”。 广度优先算法的核心思想：从初始节点开始，应用算符生成的第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点，若没有，再用算符逐一扩展第二层的所有节点…，如此依次扩展，检查下去，直到发现目标节点为止。即： 1.从图中的某一顶点v0开始，先访问v0; 2.访问所有与v0相邻的顶点v1,v2,…,vt; 3.依次访问与v1,v2,…,vt相邻接的所有未曾访问过的顶点； 4.循环以往，直至所有的顶点都被访问过为止； 这中搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。 int bfs(){ 初始化，初始状态存入队列； 队列首指针head=0;尾指针tail=1; do{ 指针head后移一位，指向待扩展结点； for(int i = 1;i <= max;++i){ //max为产生子节点的规则数 if(子节点符合条件){ tail指针增1，把新结点存入列尾； if(新结点与原已产生结点重复) 删去该结点（取消入队，tail减1）; else if(新结点是目标结点) 输出并退出； } } }while(head<tail); //队列为空 } 像科学家一样思考 像工程师一样解决问题 8 $$