深度优先搜索DFS

For personal use only in study and research; not for commercial use深度优先搜索 (DFS) 【算法入门】1.前言深度优先搜索（缩写DFS ）有点类似广度优先搜索，也是对一个连通图进行遍历的算法。它的 思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。你可以跳过第二节先看第三节，:)2.深度优先搜索VS 广度优先搜索2.1演示深度优先搜索的过程还是引用上篇文章的样例图，起点仍然是V0，我们修改一下题目意思，只需要让你找出一条 V0到 V6的道路，而无需最短路。图2-1 寻找 V0到 V6的一条路（无需最短路径）假设按照以下的顺序来搜索：1.V0->V1->V4 ，此时到底尽头，仍然到不了V6，于是原路返回到V1去搜索其他路径；2.返回到 V1后既搜索 V2 ，于是搜索路径是V0->V1->V2->V6,，找到目标节点， 返回有解。这样搜索只是 2 步就到达了，但是如果用BFS 的话就需要多几步。2.2深度与广度的比较（你可以跳过这一节先看第三节，重点在第三节）从上一篇《【算法入门】广度/ 宽度优先搜索 (BFS)》中知道，我们搜索一个图是按照树的层次来搜索的。我们假设一个节点衍生出来的相邻节点平均的个数是N 个，那么当起点开始搜索的时候，队列有一个节点，当起点拿出来后，把它相邻的节点放进去，那么队列就有N 个节点，当下一层的搜索中再加入元素到队列的时候，节点数达到了N2，你可以想想，一旦N 是一个比较大的数的时候，这个树的层次又比较深，那这个队列就得需要很大的内存空间了。于是广度优先搜索的缺点出来了：在树的层次较深&子节点数较多的情况下，消耗内存十分严重。广度优先搜索适用于节点的子节点数量不多，并且树的层次不会太深的情况。那么深度优先就可以克服这个缺点，因为每次搜的过程，每一层只需维护一个节点。但回过头想想， 广度优先能够找到最短路径，那深度优先能否找到呢？深度优先的方法是一条路走到黑，那显然无法知道这条路是不是最短的，所以你还得继续走别的路去判断是否是最短路？于是深度优先搜索的缺点也出来了：难以寻找最优解，仅仅只能寻找有解。其优点就是内存消耗小，克服了刚刚说的广度优先搜索的缺点。3.深度优先搜索3.1.举例给出如图 3-1所示的图，求图中的V0 出发，是否存在一条路径长度为4的搜索路径。图 3-1显然，我们知道是有这样一个解的：V0->V3->V5->V6。...