搜索(BFS-和-DFS)

图顶点(vertex,node)边(edge,arc)有向(directed)无向(undirected)权值(weight)容量(capacity)费用(cost)图的表示邻接矩阵空间复杂度O(V^2)邻接表空间复杂度O(E)引例迷宫问题686行8列########存储方式#.##...T到出口的最短路径#..#.####..#...#小时候玩过？#......#沿着一面墙走一定能到出口？#S######如果要得到最短的路径？BFS–广度优先搜索BFS在访问了起始顶点A之后,由A出发,依次访问A的各个未被访问过的邻接顶点B,D,…,C,然后再顺序访问B,D,…,C的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点，…如此做下去，直到图中所有顶点都被访问到为止。广度优先搜索是一种分层的搜索过程,每向前走一步可能访问一批顶点。ACDEGBFIH123456789广度优先遍历(BFS)通常用队列(先进先出,FIFO)实现Q={起点s};标记s为己访问;while(Q非空){取Q队首元素u;u出队;所有与u相邻且未被访问的点进入队列;标记u为已访问;}BFS广度优先搜索过程ACDEGBFIH123456789FEDCABGHI队列变化情况i指针箭头表示当前访问节点回到引例BFS的一种应用就是求图的最短路径（要求所有边权值相等）；分析原因：由于BFS是分层进行的所以从起点到达同一层点的路经距离应该是相同的回到引例准备条件：（变量设置根据具体情况而定）struct_queueM是问题规模，即二维迷{宫的大小intr,c,l;q[M*M]就是前面提到的用}q[M*M];于BFS的队列structmovend表示上下左右四个方向{rowcol分别记录二维迷宫intr,c;的行和列}nd[4]={-1,0,0,1,1,0,0,-1};res记录最终结果，即从起点到终点的最短距离introw,col,res;mp[M][M]存放迷宫charmp[M][M];cover用于标记已经访问过Intcover[M][M],num[M][M];num记录到达该点路程回到引例第一步：起点进入队列//qs,qe初始化为0for(inti=0;irow;i++){for(intj=0;jcol;j++)if(mp[i][j]=='S'){q[qe].r=i;q[qe].c=j;q[qe++].l=0;cover[i][j]=1;num[i][j]=0;}}具体操作还是根据具体情况定，比如有可能起点坐标已经告诉，或者找到起点后跳出循环…回到引例第二步：进行BFSwhlie(队列不空){u=对队首元素；for(所有与u邻接点v)//u的上下左右//if(v的坐标在row,col之内//并且v不是墙//并且v未被遍历)v入队}还是…具体情况具体写，比如搜索到终点跳出循环，先标记还是后标记(其实在一般情况下，都不会有太大影响)回到引例输出一个结果看看res=10最少需要十步#########表示墙#4##78910数字表示到达该点的步数（路程）#34#6###红色数字组成一条最优路径#23#567##123456##0######一个例题TOJ1132knightmoves分析：状态变为马的坐标；起点和终点意义不变；邻接点从上下左右变为“日字型”的8个方向；课下练习？恩！其他内容难点：状态的表示等优化：双向BFS（已知初末状态）其他用处：求树的直径等又一个引例不互相攻击的皇后一个8*8的国际象棋棋盘上，最多能摆放多少个不互相攻击的皇后？DFS–深度优先搜索DFS在访问图中某一起始顶点A后,由A出发,访问它的任一邻接顶点B;再从B出发,访问与B邻接但还没有访问过的顶点E;然后再从E出发,进行类似的访问,…如此进行下去,直至到达所有的邻接顶点都被访问过的顶点G为止。接着,退回一步,退到前一次刚访问过的顶点,看是否还有其它没有被访问的邻接顶点。如果有,则访问此顶点,之后再从此顶点出发,进行与前述类似的访问;如果没有,就再退回一步进行搜索。重复上述过程,直到连通图中所有顶点都被访问过为止。89ACDEGBFIH1234576虚线是回溯过程I深度优先搜索（DFS）voidDFS(PointP){for(所有P的邻接点K){if(K未被访问){标记K;DFS(K);}}}每次递归到一个点，则检查是否存在与它相邻，而且未被访问的点，有则递归访问这个点，无则返回上一层。通过比较BFS和DFS加深一下理解广度优先搜索是按层次来搜索的，根据第一层遍历出第二层，当第二层全部被访问完之后，再处理第二层，由第二层访问到第三层，依次类推，直到处理完最后一层。深度优先搜索是运用堆栈，从第一层的一个点，递归到第二层的一个点，再递归到第三层，到最后一层后，在回溯到上一层，然后从上一层递归到它的下一层的另一个点，直到它的所有点都被访问完，再回溯到上一层，依此类推，直到回溯到起点，这时所有的点都被访问完，最后形成一棵树的形状。在一些情况下，DFS和BFS与其说是对图的搜索，不如说是对状态的搜索，比如两个引例，都可以看做对状态的搜索递归调用自身例如一个求阶乘的函数f(intn)intf(intn){if(n==0)return1;returnn*f(n-1);}递归1）调用自身的思想2）设置一个递归出口3）向出口方向“移动”4）优劣（方便代码的读写，但是复杂度大）递归关于复杂度的例子计算fibonacci数列请输入k:10递归调用：res_r=55操作次数：cnt_r=109循环递推：res_1=55操作次数：cnt_1=8矩阵乘法：res_2=55操作次数：cnt_2=40DFS对状态的搜索分析：逐层递归，当递归到最后一层时，每层的状态会形成一个最终的状态，然后回溯，继续执行DFS。很明显，会出现很多个这样的“最终的状态”，保留其中较优的一个。DFS对状态的搜索voidDFS(intdepth){inti;if(depthn){if(搜索到结果)比较并记录;return;}else{for(所有状态)if(符合递归条件){标记状态;dfs(depth+1);回溯;}}}可以看到，这样的搜索，时间复杂度是(a^n)的，a为每次的状态数，n为总的递归层数。这个复杂度属于指数复杂度，当n比较大时，很荣易超时，所以，一般在n比较小的时候有深搜。而且很多情况下需要剪枝。回到引例分析：把一行看做一层递归调用每一层的状态就是这一行皇后的位置只需要一个可行解，而非最优解手动模拟一下DFS过程回到引例一个可行解（代码不难实现，建议课下自己写一写）#...........#..........#.....#....#...........#..#.........#....DFS对状态的搜索关于剪枝：剪枝就是在当前搜索状态下，已经无法得到解，或者已经无法得到最优解，则不再继续递归调用下去，而是另辟新径。一个例题toj2273MakingChange题目大意：一共有四种硬币25美分，10美分，5美分，1美分四种硬币的个数num[0]num[1]num[2]num[3]给定某个数n，问用这些硬币组合，能否得到n，如果能，使用硬币最少的情况下，怎么组合？样例输入：599937样例输出：Dispense1quarters,1dimes,0nickels,and2pennies.一个例题含有前面对讨论DFS状态的搜索中需要达到的“最优”要求，也涉及到剪枝分析：一共四层在k层，依次用0，1，…num[k]个硬币，递归调用DFS（k+1）,直到最后一层在最后一层判断能否组合成n，如果能，记录当前状态和最优状态的较优值一个例题voiddfs(intk){if(k==3){if(能组合成n)记录较优结果回溯}for(inti=0;i=num[i];i++){取i枚当前价值的硬币dfs（k+1）}}一个例题voiddfs(intk){if(k==3){if(能组合成n)记录较优结果回溯}for(inti=0;i=num[i];i++){取i枚当前价值的硬币dfs（k+1）}}一个例题细节问题：什么叫取出当前价值的i枚硬币？如果当前硬币取i枚后，所得到的数已经大于n？回溯过程需要还原成上一层状态，怎么实现？是不是真的需要每层执行O（num[k]）次？DFS其他问题复杂度大，在使用之前分析能否接受状态的表示，以及每次回溯后，状态都要还原成上一层状态剪枝more…具体情况，写法当然不一样一些练习题目BFS:2194Mine2470RobotinMaze1132KnightMovesDFS:1398Square3169BacktotheBarn2273MakingChange建议初学同学可以先自己动手写写两个引例other练习题目发信人:cnhawk(焚书煲粥|cnhawk=CaiNiaoHawk),信区:ACM标题:TOJ简单题题号发信站:天大求实BBS(TueOct1013:20:342006),本站(bbs.tju.edu.cn)上次给我同学列的，都是我刚接触时做的题，供新加入的同学们上上手，也供学习C/C++的同学提高代码能力~顺序是乱排的。大家凑合着看：1939.1730.1476.1169.2051.1574.1818.2056.1748.1412.1649.1015.1715.1457.1823.1233.1805.1380.1257.1549.1637.1833.1355.1208.1516.2076.1154.2010.1517.1171.1856.1477.2483.2468.膜拜cnhawk…Thankyouforyourattending.