电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

深度优先搜索DFS

深度优先搜索DFS_第1页
1/9
深度优先搜索DFS_第2页
2/9
深度优先搜索DFS_第3页
3/9
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。...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

深度优先搜索DFS

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部