深度优先搜索(dfs)

《深度优先搜索(dfs)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、深度优先搜索(DFS)【算法入门】1.前言深度优先搜索（缩写DFS）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。你可以跳过第二节先看第三节，:)2.深度优先搜索VS广度优先搜索2.1演示深度优先搜索的过程还是引用上篇文章的样例图，起点仍然是V0，我们修改一下题目意思，只需要让你找出一条V0到V6的道路，而无需最短路。图2-1寻找V0到V6的一条路（

2、无需最短路径）假设按照以下的顺序来搜索：1.V0->V1->V4，此时到底尽头，仍然到不了V6，于是原路返回到V1去搜索其他路径；2.返回到V1后既搜索V2，于是搜索路径是V0->V1->V2->V6,，找到目标节点，返回有解。这样搜索只是2步就到达了，但是如果用BFS的话就需要多几步。2.2深度与广度的比较（你可以跳过这一节先看第三节，重点在第三节）从上一篇《【算法入门】广度/宽度优先搜索(BFS)》中知道，我们搜索一个图是按照树的层次来搜索的。我们假设一个节点衍生出来的相邻节点平均的个数是N个，那么当起点开始搜索的时

3、候，队列有一个节点，当起点拿出来后，把它相邻的节点放进去，那么队列就有N个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了N2，你可以想想，一旦N是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。于是广度优先搜索的缺点出来了：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想，广度优先能够找到最短路径，那深度优先能否找到呢

4、？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。3.深度优先搜索3.1.举例给出如图3-1所示的图，求图中的V0出发，是否存在一条路径长度为4的搜索路径。图3-1显然，我们知道是有这样一个解的：V0->V3->V5->V6。3.2.处理过程3.3.对应例子的伪代码这里先给出上边处理过程的对应伪代码。[cpp]viewplaincopy1/**

5、2*DFS核心伪代码3*前置条件是visit数组全部设置成false4*@paramn当前开始搜索的节点5*@paramd当前到达的深度，也即是路径长度6*@return是否有解7*/1boolDFS(Noden,intd){2if(d==4){//路径长度为返回true，表示此次搜索有解3returntrue;4}56for(NodenextNodeinn){//遍历跟节点n相邻的节点nextNode，7if(!visit[nextNode]){//未访问过的节点才能继续搜索89//例如搜索到V1了，那么V1要设置成已

6、访问10visit[nextNode]=true;1112//接下来要从V1开始继续访问了，路径长度当然要加1314if(DFS(nextNode,d+1)){//如果搜索出有解15//例如到了V6，找到解了，你必须一层一层递归的告诉上层已经找到解16returntrue;17}1819//重新设置成未访问，因为它有可能出现在下一次搜索的别的路径中20visit[nextNode]=false;2122}23//到这里，发现本次搜索还没找到解，那就要从当前节点的下一个节点开始搜索。24}25returnfalse;//本

7、次搜索无解26}3.4.DFS函数的调用堆栈此后堆栈调用返回到V0那一层，因为V1那一层也找不到跟V1的相邻未访问节点此后堆栈调用返回到V3那一层此后堆栈调用返回到主函数调用DFS(V0,0)的地方，因为已经找到解，无需再从别的节点去搜别的路径了。4.核心代码这里先给出DFS的核心代码。[cpp]viewplaincopy1/**2*DFS核心伪代码3*前置条件是visit数组全部设置成false4*@paramn当前开始搜索的节点5*@paramd当前到达的深度6*@return是否有解7*/8boolDFS(Node

8、n,intd){9if(isEnd(n,d)){//一旦搜索深度到达一个结束状态，就返回true10returntrue;11}1213for(NodenextNodeinn){//遍历n相邻的节点nextNode14if(!visit[nextNode]){//15visit[nextNode]=true;//在下