在上一次的文章中,我们介绍了图的一些基础知识及图的基础搜索算法之中的广度优先搜索BFS。本文我们介绍另外一种基础的图搜索算法——DFS 深度优先搜索
DFS 算法
基本思想
众所周知,BFS算法是按广度进行搜索遍历的。其对于一个顶点的分岔路径,是采用类似于轮询的思想,通过依次遍历的方式去处理;而对于DFS算法而言,故名思义,其按照图的深度进行遍历搜索的。其在一个顶点遇到分岔路径时,会选择其中一条未被访问过的路径继续前进搜索,周而复始、一条路走到黑,直到其发现已经无路可走;此时,其根据走过的路径回溯到上一个顶点;然后判断此处是否存在新的未被访问过的分岔路径可供前进搜索;如果存在,则前进搜索,否则,继续回溯,回溯到上上一个顶点。DFS算法的图解过程,如下所示:
算法流程
该算法通过递归即可实现按深度搜索顶点,算法流程如下:
- 指定搜索起点,记为顶点V
- 将顶点V的访问状态标记为已搜索
- 获取顶点V所有的未被搜索过的邻接点列表 toSearchList
- 遍历邻接点列表 toSearchList 依次取出元素执行:将顶点记为V、记录访问该顶点路径的前驱顶点、重复 Step 2-4
Java Demo
现已上文DFS图解的无向图为例,通过Java实现DFS算法
1 | /** |
算法结果:
参考文献
- 算法(第4版) Robert Sedgewick、Kevin Wayne 著