算法与数据结构第七章算法1深度优先搜索DFS

2025-09-27 约 7422 字预计阅读 15 分钟

https://bing.ee123.net/img/rand?artid=152171157

《算法与数据结构》第七章[算法1]：深度优先搜索(DFS)

1、深度优先遍历

我们先来设想一个情景，你来到了一个一座废弃的地下迷宫，迷宫中有着许多暗室，暗室间有通道相连，而传说中宝藏就藏在某个暗室中，此时的你手中没有地图，只有一支粉笔、一支手电筒，为了找到宝藏，你决定从迷宫的入口处开始探索，你会怎么做呢？我现在给出一个思路：

每进入一个新的暗室，你就用粉笔在门口做一个记号，表示你已经来过这里了，防止以后再走到这里时重复探索。
每当你进入一个暗室后，你会先用手电筒照亮这个暗室，看看这里有没有宝藏，如果有宝藏，那就太好了，直接拿走就行了。
如果这个暗室没有宝藏，你就会查看这个暗室的所有通道，选择一个通道进入下一个暗室，继续进行上述操作。
如果你进入的暗室没有通道了，或者所有通道都已经被你探索过了(即通道通向的暗室已经被你做过记号了)，那你就会返回到上一个暗室，继续选择其他未探索过的通道，进入下一个暗室，继续进行上述操作。
如果宝藏被找到，或者发现所有暗室都被你探索过了(即所有暗室的门口都有你的记号了)，那你就会结束探索，离开迷宫。

这种“一路走到底，不撞南墙不回头”的探索策略，就是深度优先遍历中“深度”的体现。

深度优先遍历(Depth-First Search, DFS)：是一种优先深入图中某一分支的遍历策略。

可能有些同学已经意识到了，我口中的地下迷宫就是一个图，而暗室就是图中的顶点，暗室间的通道就是图中的边，而宝藏就是我们要找的目标，粉笔做的记号就是访问标志数组visited[]，手电筒照亮暗室就是访问顶点。

还有些同学十分敏感，发现我提到了“返回到上一个暗室”，再进行，这不是我们在树的遍历中提到的递归结束后的返回吗？甚至再进行仔细思考，发现我们的整个策略就是“先访问当前顶点，再找其邻接顶点”，这不是树的先根遍历、二叉树的前序遍历吗？没错，聪明的你已经发现了，图的深度优先遍历和树的先根遍历、二叉树的前序遍历是类似的，都是“先访问当前结点，再找其子结点”，只是图中结点的子结点不唯一，且可能存在环路，所以我们需要访问标志数组visited[]来防止重复访问。

DFS基本思想就是：从一个未被访问的顶点出发，访问该顶点并标记为已访问，然后递归地对所有未被访问的邻接顶点进行深度优先遍历，直到所有可达顶点都被访问为止。

事实上，我们这里只考虑到了连通图的情况，若是非连通图，则需要对图中所有顶点进行一次循环，若发现有未被访问的顶点，则选择一个未被访问的顶点出发进行DFS，直到所有顶点均被访问为止。

我们给出邻接矩阵存储结构的图的深度优先遍历代码：

#define MAXVEX 100 // 最大顶点数
int visited[MAXVEX]; // 访问标志数组

void DFS(GraphAdjMatrix G, int i) // 从第i个顶点出发深度优先遍历图G
{
    int j;
    visited[i] = 1; // 标记当前顶点已访问
    printf("%c ", G.vexs[i]); // 访问当前顶点
    for (j = 0; j < G.numVertexes; j++) // 查找当前顶点的所有邻接顶点
    {
        if (G.arc[i][j] == 1 && !visited[j]) // 若邻接且未被访问
        {
            DFS(G, j); // 递归访问该邻接顶点
        }
    }
}

void DFSTraverse(GraphAdjMatrix G) // 图G的深度优先遍历
{
    int i;
    for (i = 0; i < G.numVertexes; i++) // 初始化访问标志数组
    {
        visited[i] = 0;
    }
    for (i = 0; i < G.numVertexes; i++) // 对图中每个顶点进行检查
    {
        if (!visited[i]) // 若该顶点未被访问
        {
            DFS(G, i); // 从该顶点出发进行深度优先遍历
        }
    }
}

从代码中我们可以看出，DFSTraverse()函数用于初始化访问标志数组visited[]，并对图中每个顶点进行检查，若发现有未被访问的顶点，则选择一个未被访问的顶点出发进行DFS。而DFS()函数则是递归地对所有未被访问的邻接顶点进行深度优先遍历。

我们再给出邻接表存储结构的图的深度优先遍历代码：

#define MAXVEX 100 // 最大顶点数
int visited[MAXVEX]; // 访问标志数组

void DFS(GraphAdjList G, int i) // 从第i个顶点出发深度优先遍历图G
{
    EdgeNode* p;
    visited[i] = 1; // 标记当前顶点已访问
    printf("%c ", G.vexs[i].data); // 访问当前顶点
    p = G.vexs[i].firstedge; // 指向当前顶点的边表
    while (p) // 遍历边表
    {
        if (!visited[p->adjvex]) // 若邻接且未被访问
        {
            DFS(G, p->adjvex); // 递归访问该邻接顶点
        }
        p = p->next; // 指向下一条边
    }
}

void DFSTraverse(GraphAdjList G) // 图G的深度优先遍历
{
    int i;
    for (i = 0; i < G.numVertexes; i++) // 初始化访问标志数组
    {
        visited[i] = 0;
    }
    for (i = 0; i < G.numVertexes; i++) // 对图中每个顶点进行检查
    {
        if (!visited[i]) // 若该顶点未被访问
        {
            DFS(G, i); // 从该顶点出发进行深度优先遍历
        }
    }
}

我们来对比一下两种不同结构下的DFS，对于nnn个结点和eee条边的图来说，邻接矩阵存储结构下的DFS时间复杂度为O(n2)O(n^2)O(n2)，因为需要遍历邻接矩阵的每一行来查找邻接顶点；而邻接表存储结构下的DFS时间复杂度为O(n+e)O(n+e)O(n+e)，因为每个顶点和每条边都只被访问一次。所以，在实际应用中，若图较为稀疏，邻接表存储结构下的DFS更为高效。

对于有向图来说，DFS的实现与无向图类似，只需在判断邻接顶点时，检查弧的方向即可。

2、深度优先遍历过程

考试的时候，你会遇到这么一种题，给你一个图，让你写出深度优先遍历的过程，或者让你写出深度优先遍历的结果，这种题目一般会给出图或其邻接矩阵或邻接表，然后让你从某个顶点开始进行DFS。

我们以如下图为例，同时给出其邻接矩阵：

图1：无向图

我们就从调用DFSTraverse(G)开始进行深度优先遍历，推出遍历的过程和结果。

图2：DFS遍历过程1

初始化访问标志数组不用讲解，接下来的代码就是：

for (i = 0; i < G.numVertexes; i++) // 对图中每个顶点进行检查
{
    if (!visited[i]) // 若该顶点未被访问
    {
        DFS(G, i); // 从该顶点出发进行深度优先遍历
    }
}

i从0开始，判断isvisited[0]是否为0即判断v0v_0v0有没有被访问，未被访问，进入分支调用DFS(G, 0)，也就是我们从顶点v0v_0v0开始，访问v0v_0v0，并标记v0v_0v0为已访问，然后查看v0v_0v0的邻接顶点，发现有v3v_3v3、v4v_4v4和v5v_5v5，可以看出标红的三条边就是我们可以探索的方向。那么这时候我们该如何走呢？为保证我们的过程符合DFS的规则，这时候就需要来看代码了，可以看到输出(访问)语句后有这么一个循环：

for (j = 0; j < G.numVertexes; j++)
{
    if (G.arc[i][j] == 1 && !visited[j])
    {
        DFS(G, j);
    }
}

它的作用就是在邻接矩阵第iii行从第0个找到第G.numVertexes(顶点数)个，找出邻接矩阵中谁是1，即找出谁和viv_ivi有边，既然它的j是从0开始的，那我们就从0来看。G.arc[0]=[0,0,0,1,1,1]G.arc[0]=[0, 0, 0, 1, 1, 1]G.arc[0]=[0,0,0,1,1,1]，可以看出，当j为0时G.arc[i][j]=0，不符合条件，j自增到1，此时G.arc[i][j]=0依旧不符合条件，…，直到j走到3，发现G.arc[i][j]=1符合条件，再看看visited[j]此时vjv_jvj即v3v_3v3还未被访问，所以调用DFS(G, 3)，也就是说，我们的策略是选择所有可以前往的且下标最小的未被访问的顶点进行探索。

图3：DFS遍历过程2

调用DFS(G, 3)后，我们进入了顶点v3v_3v3并进行访问，发现还是有多条路线(v0v_0v0、v1v_1v1和v2v_2v2)可以走，但此时的我们已不再彷徨，我们知道下标最小的是v0v_0v0，可是v0v_0v0已被访问过了(visited[0]=1)，除去这个，下标最小且未被访问的就是v1v_1v1了，我们调用DFS(G, 1)进入顶点v1v_1v1。

图4：DFS遍历过程3

进入顶点v1v_1v1并进行访问后，我们发现不同于前面的过程，顶点v1v_1v1只有一条路可以走，那就是v3v_3v3，可是v3v_3v3已被访问过了(visited[3]=1)，这样一来，我们就没有路可走了，体现在代码中就是for循环走完了都没有符合条件的j，这时我们对DFS(G, 1)的调用就会结束，此时就会返回到我们进入DFS(G, 1)前在干的事，即返回到DFS(G, 3)中继续执行for循环。也就是说，我们对于这种情况的策略是回到上一顶点，选择该顶点其他未被访问的邻接顶点进行探索。

图5：DFS遍历过程4

回到顶点v3v_3v3后，我们继续执行for循环(j此时为2)，依旧采取我们原来的探索策略，发现下标最小且未被访问的邻接顶点就是v2v_2v2，于是调用DFS(G, 2)进入顶点v2v_2v2。

图6：DFS遍历过程5

进入顶点v2v_2v2并进行访问后，我们又遇到了与v1v_1v1顶点遇到的相同的情况，即无路可走，我们再次按照我们刚才找出的策略，回到上一顶点v3v_3v3，继续选择其他未被访问的邻接顶点进行探索。

图7：DFS遍历过程6

回到顶点v3v_3v3后，我们发现v3v_3v3的所有邻接顶点都已被访问过了(visited[0]=1, visited[1]=1, visited[2]=1)，这时我们依旧采取策略2回到上一顶点v0v_0v0(代码中为DFS(G, 3)调用结束，回到我们进入递归后最开始调用的DFS(G, 0))，继续选择其他未被访问的邻接顶点进行探索。

图8：DFS遍历过程7

回到顶点v0v_0v0后，我们继续执行for循环(j此时为4)，发现下标最小且未被访问的邻接顶点就是v4v_4v4，于是调用DFS(G, 4)进入顶点v4v_4v4。

图9：DFS遍历过程8

进入顶点v4v_4v4并进行访问后，我们发现情况和v1v_1v1、v2v_2v2顶点遇到的情况相同，再回到上一顶点v0v_0v0。

图10：DFS遍历过程9

回到顶点v0v_0v0后，我们继续执行for循环(j此时为5)，发现下标最小且未被访问的邻接顶点是v5v_5v5，调用DFS(G, 5)进入顶点v5v_5v5。

图11：DFS遍历过程10

进入顶点v5v_5v5并进行访问后，我们发现情况和v1v_1v1、v2v_2v2、v4v_4v4顶点遇到的情况相同，再回到上一顶点v0v_0v0(代码即最开始调用的DFS(G, 0))。此时对于我们来说，所有顶点都已被访问过了，就算结束了，可是计算机的执行还未结束，我们此时还在DFS(G, 0)中，继续执行for循环(j此时为6)，发现j已不小于顶点数了，for循环结束，DFS(G, 0)调用结束，回到最开始的函数调用DFSTraverse(G)中继续执行for循环。此时的for循环中i为1，发现visited[1]=1，继续i自增，i为2，发现visited[2]=1，继续i自增，…，直到i为5，发现visited[5]=1，继续i自增到6，发现i已不小于顶点数了，for循环结束，整个DFSTraverse(G)调用过程才算结束。这时会有同学感到疑惑，调用DFS(G, 0)时，就已经可以把所有顶点都访问完，为什么不能和之前的树的遍历一样，在进行DFS时直接调用DFS(G, i)呢？而是要多此一举地在DFSTraverse(G)中调用它呢？

不知道大家还记不记得在给出代码前，我们说过“我们这里只考虑到了连通图的情况，若是非连通图，则需要对图中所有顶点进行一次循环，若发现有未被访问的顶点，则选择一个未被访问的顶点出发进行DFS，直到所有顶点均被访问为止。”不同于树，图中可能存在没有连通的结点、或有向图中可能存在无法到达的结点，所以我们才需要在DFSTraverse(G)中对图中所有顶点进行一次循环，防止出现只调用DFS(G, i)时，无法访问到图中所有顶点的情况。

我们又再一次领略了递归的魅力，DFS的过程就是递归调用的过程，回到上一顶点就是递归调用结束后的返回。以上就是从顶点v0v_0v0开始进行DFS的完整过程，最终的遍历结果为：

v0→v3→v1→v2→v4→v5v_0 \rightarrow v_3 \rightarrow v_1 \rightarrow v_2 \rightarrow v_4 \rightarrow v_5v0→v3→v1→v2→v4→v5

其实这个过程中我们发现，DFS的遍历结果与图的存储结构无关，只与顶点的邻接顺序有关，也就是说，不管是邻接矩阵存储结构还是邻接表存储结构，只要顶点的邻接顺序不变，DFS的遍历结果就不会变，若是我们将每个顶点的下标进行调整，结果也会发生一定变化。例如我们将顶点数组顺序改为[v5,v4,v3,v2,v1,v0][v_5,v_4,v_3,v_2,v_1,v_0][v5,v4,v3,v2,v1,v0]，它的DFSTraverse(G)调用遍历结果就变成了下面这样：

v5→v0→v3→v1→v2→v4v_5 \rightarrow v_0 \rightarrow v_3 \rightarrow v_1 \rightarrow v_2 \rightarrow v_4v5→v0→v3→v1→v2→v4

邻接表的DFS过程则不再赘述，给出上述过程中图的邻接表，遍历结果与邻接矩阵是一致的，大家可以自行根据上述过程探索。

图12：邻接表

3、DFS的栈实现

我们来回顾一下DFS的递归过程中我们提到的两个策略：

选择所有可以前往的且下标最小的未被访问的顶点进行探索。
若无路可走，则回到上一顶点，选择该顶点其他未被访问的邻接顶点进行探索。

我们发现当我们到达一个顶点时，我们会以当前顶点为起点，选择一个未被访问的邻接顶点进行探索，并不关心当前顶点后续的邻接顶点，即只关心最新到达的顶点；而当我们无路可走时，我们再回头去看之前的顶点，再去关心之前顶点的其他邻接顶点，这样一来，就可以将这个顺序看作是一个“后进先出”的顺序，后面到达的顶点先被处理，前面到达的顶点在没有选择时才(后)被处理，这不正是栈的特点吗？

我们在“栈”一章中提到过，递归其实就是系统利用了栈来实现的，所以我们其实是可以用栈来模拟递归的过程的，从而实现DFS的非递归版本。同时作为对栈的复习和巩固。

我们先给出顺序栈及涉及到的操作定义：

#define MAXVEX 100 // 最大顶点数
int visited[MAXVEX]; // 访问标志数组

typedef int StackElemType;
typedef struct {
	StackElemType data[MAXVEX];
	int top;
}Stack;

void InitStack(Stack* S) // 初始化栈
{
    S->top = -1;
}

int StackEmpty(Stack* S) // 判断栈是否为空
{
    return S->top == -1;
}

int Push(Stack* S, StackElemType e) // 入栈
{
    if (S->top == MAXSIZE - 1) // 栈满
        return 0;
    S->data[++S->top] = e;
    return 1;
}

int Pop(Stack* S, StackElemType* e) // 出栈
{
    if (StackEmpty(S)) // 栈空
        return 0;
    *e = S->data[S->top--];
    return 1;
}

我们再给出邻接矩阵存储结构的图的DFS的栈实现代码：

void DFS(GraphAdjMatrix G, int i) // 从第i个顶点出发深度优先遍历图G
{
    int j;
    Stack S;
    InitStack(&S); // 初始化栈
    Push(&S, i); // 将起始顶点入栈
    while (!StackEmpty(&S)) // 栈不为空
    {
        Pop(&S, &i); // 出栈
        if (!visited[i]) // 若该顶点未被访问
        {
            visited[i] = 1; // 标记当前顶点已访问
            printf("%c ", G.vexs[i]); // 访问当前顶点
            for (j = G.numVertexes - 1; j >= 0; j--) // 查找当前顶点的所有邻接顶点
            {
                if (G.arc[i][j] == 1 && !visited[j]) // 若邻接且未被访问
                {
                    Push(&S, j); // 将该邻接顶点入栈
                }
            }
        }
    }
}

void DFSTraverse(GraphAdjMatrix G) // 图G的深度优先遍历
{
    int i;
    for (i = 0; i < G.numVertexes; i++) // 初始化访问标志数组
    {
        visited[i] = 0;
    }
    for (i = 0; i < G.numVertexes; i++) // 对图中每个顶点进行检查
    {
        if (!visited[i]) // 若该顶点未被访问
        {
            DFS(G, i); // 从该顶点出发进行深度优先遍历
        }
    }
}

相比我们一开始的思路，代码中有一点点不同，那就是在查找当前顶点的所有邻接顶点时，我们是从后往前查找的，这样做的目的是为了保证我们选择的是下标最小的未被访问的邻接顶点进行探索，因为栈是“后进先出”的结构，若是我们从前往后查找并入栈，那么下标最大的未被访问的邻接顶点会最先被处理，这就违背了我们的DFS策略。若是目前还无法理解，我们可以来推一下在该方法下的DFS过程。

我们依旧以下图为例：

图13：无向图

我们给出初始化的访问标志数组和栈的状态：

图14：初始化

我们也依旧从调用DFSTraverse(G)开始进行深度优先遍历，推出遍历的过程和结果。

前面的内容不再讲解，直接进入DFS(G, 0)调用过程

图15：栈实现DFS遍历过程1

可以看到，进入DFS(G, 0)，先将顶点v0v_0v0入栈(实际上入栈的是v0v_0v0的下标0)，然后进入while循环，此时栈不为空，然后将栈顶元素出栈(即v0v_0v0)，判断v0v_0v0是否被访问，未被访问，访问v0v_0v0并标记v0v_0v0为已访问，然后倒序查看v0v_0v0的邻接顶点，j从5开始，发现v5v_5v5是v0v_0v0的邻接顶点且未被访问，则将v5v_5v5入栈，然后分别是v4v_4v4和v3v_3v3，它们逐个入栈，j依次减到2、1、0时，发现都不是v0v_0v0的邻接顶点，循环结束。

图16：栈实现DFS遍历过程2

此时一次while循环结束，再次判断栈是否为空，栈不为空，继续出栈，此时出栈的就是v3v_3v3，这样一来大家就能理解为什么要倒序查找邻接顶点并入栈了，因为v3v_3v3是下标最小的未被访问的邻接顶点，若是我们从前往后查找并入栈，那么v5v_5v5会最先被处理，而这样则与我们一开始的DFS策略相异。然后判断知道v3v_3v3未被访问，访问并标记v3v_3v3，再以倒序查询v3v_3v3的未被访问的邻接点，则有v2v_2v2、v1v_1v1，它们依次入栈。

图17：栈实现DFS遍历过程3

此时又一次while循环结束，再次判断栈是否为空，栈不为空，继续出栈，此时v1v_1v1出栈，然后判断v1v_1v1未被访问，访问并标记v1v_1v1，再以倒序查询v1v_1v1的未被访问的邻接点，发现只有v3v_3v3且已被访问，无路可走，体现在代码中就是for循环走完了都没有符合条件的j，这时一次while循环结束，此轮循环没有元素入栈。

图18：栈实现DFS遍历过程4

再次判断栈是否为空，栈不为空，继续出栈，此时v2v_2v2出栈，且判断其未被访问，访问并标记v2v_2v2，再以倒序查询v2v_2v2的未被访问的邻接点，同样只有已被访问过的v3v_3v3，本轮while循环结束。

图19：栈实现DFS遍历过程5

后面的过程与上述完全相似，直至栈为空，DFS(G, 0)调用结束，回到DFSTraverse(G)中继续执行for循环，最终的遍历结果依旧为：

v0→v3→v1→v2→v4→v5v_0 \rightarrow v_3 \rightarrow v_1 \rightarrow v_2 \rightarrow v_4 \rightarrow v_5v0→v3→v1→v2→v4→v5

若是我们将for循环改为从前往后查找邻接顶点并入栈，那么最终的遍历结果就会变成：

v0→v5→v4→v3→v2→v1v_0 \rightarrow v_5 \rightarrow v_4 \rightarrow v_3 \rightarrow v_2 \rightarrow v_1v0→v5→v4→v3→v2→v1

这样的结果并不符合我们提出的DFS策略。其实也不能说它不是DFS，只不过它选择的是下标最大的未被访问的邻接顶点进行探索，这也是一种DFS策略，只不过不为我们常用罢了。

其实从过程中就能看出，由栈实现的DFS性能表现与递归实现的DFS是一样的，只不过由于递归所使用的系统隐式栈更加成熟(时间优化和空间优化更佳)，所以在实际应用中，递归实现的DFS可能表现更佳。但是！递归是有深度限制的，若递归层数过深，可能会导致栈溢出，而栈实现的DFS则没有这个问题，所以在处理大规模图时，栈实现的DFS可能更具健壮性。