数据结构与算法：图的遍历—深度优先搜索

2025-12-13 算法

一、图的遍历遍历是指从某个节点出发，按照一定的的搜索路线，依次访问对数据结构中的全部节点，且每个节点仅访问一次。
前面已经讲过了二叉树的节点遍历。
类似的，图的遍历是指，从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。
图的遍历过程中，根据搜索方法的不同，又可以划分为两种搜索策略：

深度优先搜索
广度优先搜索

二、深度优先搜索（DFS ， Depth First Search）深度优先搜索，从起点出发，从规定的方向中选择其中一个不断地向前走，直到无法继续为止，然后尝试另外一种方向，直到最后走到终点。就像走迷宫一样，尽量往深处走。
DFS 解决的是连通性的问题，即，给定两个点，一个是起始点，一个是终点，判断是不是有一条路径能从起点连接到终点。起点和终点，也可以指的是某种起始状态和最终的状态。问题的要求并不在乎路径是长还是短，只在乎有还是没有。
假设我们有这么一个图，里面有A、B、C、D、E、F、G、H 8 个顶点，点和点之间的联系如下图所示，对这个图进行深度优先的遍历。

数据结构与算法：图的遍历—深度优先搜索

文章插图

必须依赖栈（Stack），特点是后进先出（LIFO）。
第一步，选择一个起始顶点，例如从顶点 A 开始。把 A 压入栈，标记它为访问过（用红色标记），并输出到结果中。

数据结构与算法：图的遍历—深度优先搜索

文章插图

第二步，寻找与 A 相连并且还没有被访问过的顶点，顶点 A 与 B、D、G 相连，而且它们都还没有被访问过，我们按照字母顺序处理，所以将 B 压入栈，标记它为访问过，并输出到结果中。

数据结构与算法：图的遍历—深度优先搜索

文章插图

第三步，现在我们在顶点 B 上，重复上面的操作，由于 B 与 A、E、F 相连，如果按照字母顺序处理的话， A 应该是要被访问的，但是 A 已经被访问了，所以我们访问顶点 E ，将 E 压入栈，标记它为访问过，并输出到结果中。

数据结构与算法：图的遍历—深度优先搜索

文章插图

第四步，从 E 开始， E 与 B、G 相连，但是B刚刚被访问过了，所以下一个被访问的将是G ，把G压入栈，标记它为访问过，并输出到结果中。

数据结构与算法：图的遍历—深度优先搜索

文章插图

第五步，现在我们在顶点 G 的位置，由于与 G 相连的顶点都被访问过了，类似于我们走到了一个死胡同，必须尝试其他的路口了。所以我们这里要做的就是简单地将 G 从栈里弹出，表示我们从 G 这里已经无法继续走下去了，看看能不能从前一个路口找到出路。

数据结构与算法：图的遍历—深度优先搜索

文章插图

如果发现周围的顶点都被访问了，就把当前的顶点弹出。
第六步，现在栈的顶部记录的是顶点 E ，我们来看看与 E 相连的顶点中有没有还没被访问到的，发现它们都被访问了，所以把 E 也弹出去。

数据结构与算法：图的遍历—深度优先搜索

文章插图

第七步，当前栈的顶点是 B ，看看它周围有没有还没被访问的顶点，有，是顶点 F ，于是把 F 压入栈，标记它为访问过，并输出到结果中。

推荐阅读

上一篇：没有了

下一篇：ERP与CRM软件集成的关键优势