7.3.1　深度优先遍历

所谓的深度优先遍历是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历的推广。

深度优先搜索的基本思想是：

（1）从图中某个顶点v0出发，首先访问v0。

（2）找出刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点。重复此步骤，直到刚访问过的顶点没有未被访问的邻接点。

（3）返回前一个访问过的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。转到第（2）步骤。

现以图7－22为例说明深度优先搜索过程。假定v1是出发点，首先访问v1。因v1有两个邻接点v2、v3均末被访问过，可以选择v2作为新的出发点，访问v2之后，再找v2的末访问过的邻接点。同v2邻接的有v1、v4和v5，其中v1已被访问过，而v4、v5尚未被访问过，可以选择v4作为新的出发点。重复上述搜索过程，继续依次访问v8、v5。访问v5之后，由于与v5相邻的顶点均已被访问过，搜索退回到v1，访问v1的另一个邻接点v3。接下来依次访问v6和v7，最后得到的顶点的访问序列为：v1→v2→v4→v8→v5→v3→v6→v7。

图7－22 深度优先搜索

可以看到，深度优先遍历其实就是一个递归的过程，相当于树的前序遍历。它从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直到图中所有和v有路径相通的顶点都被访问到。

图的深度优先搜索的结构定义如下。

算法7.3 采用邻接表的DepthFirstSearch

以邻接表作为存储结构，查找每个顶点的邻接点的时间复杂度为O（e），其中e是无向图中的边数或有向图中弧数，则深度优先搜索图的时间复杂度为O（n＋e）。

用非递归过程实现深度优先搜索算法如下。

算法7.4 非递归形式的DepthFirstSearch