深入理解图的深度优先搜索（DFS）：从原理到 C 语言实战

2026-02-17 14:06:41 0条评论 2次阅读 0人点赞

在算法和计算机科学领域，图是一种极其强大且灵活的数据结构。你是否想过，GPS 导航是如何为你找到路径的？或者社交网络是如何推荐“你可能认识的人”的？这些问题的背后往往都涉及到图的遍历算法。

今天，我们将深入探讨图遍历中最基础且最重要的算法之一：深度优先搜索（Depth First Search，简称 DFS）。我们将一起探索它的工作原理，通过 C 语言从零开始构建它，并讨论在实际开发中如何高效地使用它。

什么是深度优先搜索（DFS）？

你可以把 DFS 想象成你在探索一个巨大的迷宫。

  • 起点：你选择一个入口出发。
  • 深入：你沿着一条路一直走，只要遇到没去过的路口，就继续往深处走。
  • 回溯：当你走到死胡同（或者所有路都走过了），你会原路返回到上一个路口，看看有没有其他没走的路。
  • 循环：重复这个过程，直到所有能到达的地方都 explored（探索）完毕。

与树的遍历非常相似，对吧？唯一的区别在于，树是不会分叉回去的，而图可能会。

核心挑战：环与重复访问

图的结构比树更复杂，因为它可能包含环（Cycles）。这意味着你可能会从节点 A 走到 B，再从 C 走回 A。如果不加控制，我们的程序可能会陷入“无限循环”，像个鬼打墙一样在节点之间来回跑。

解决方案：我们需要一个“记事本”。在计算机术语中，这通常是一个布尔类型的数组 visited[]。当我们访问一个节点时，我们在记事本上打勾；下次遇到这个节点时，先看一眼记事本，如果来过了，就忽略它。

DFS 的实际应用场景

在我们敲代码之前，让我们先看看 DFS 在现实世界中解决了哪些问题：

  • 路径寻找：在迷宫游戏中寻找从起点到终点的路。
  • 拓扑排序：判断课程修习的先后顺序，或者任务依赖关系（A 任务必须在 B 之前完成）。
  • 检测环：在死锁检测中，判断资源分配图是否存在环路。
  • 连通性检查：判断图中两个节点是否相连（比如社交网络中的六度人脉理论）。

图的表示方法：邻接表

在 C 语言中实现图，最常用的方法是邻接表。你可以把它想象成一张散列表，或者是一个数组的链表。

  • 每个节点（顶点）对应数组中的一个索引。
  • 每个数组元素指向一个链表，链表中存储着所有与该节点直接相连的邻居节点。

这种方法的优点是空间效率高，特别是对于稀疏图（边数远小于节点数的平方）来说。

核心代码实现（C 语言）

让我们来实现一个完整的 C 程序。我们将使用邻接表来构建图，并使用递归来实现 DFS 逻辑。

1. 数据结构定义

首先，我们需要定义图的基本积木。

#include 
#include 
#include 

// 邻接表中链表节点的结构
struct Node {
    int dest;            // 目标顶点的数据
    struct Node* next;   // 指向下一个邻居节点的指针
};

// 邻接表的结构
struct AdjList {
    struct Node* head;   // 指向链表头部的指针
};

// 图的结构
struct Graph {
    int numVertices;     // 图中顶点的总数
    struct AdjList* array; // 邻接表数组
};

2. 辅助函数：创建节点与图

我们需要一些工厂函数来帮我们初始化内存。

// 创建新的邻接表节点
struct Node* createNode(int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建具有特定顶点数量的图
struct Graph* createGraph(int numVertices) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->numVertices = numVertices;

    // 为邻接表分配内存
    graph->array = (struct AdjList*)malloc(numVertices * sizeof(struct AdjList));

    // 初始化每个邻接表为空
    for (int i = 0; i array[i].head = NULL;

    return graph;
}

3. 添加边

这是图构建的关键步骤。请注意，我们在头部插入新节点，这在链表操作中是 O(1) 的时间复杂度，非常高效。

// 添加边（有向图）
void addEdge(struct Graph* graph, int src, int dest) {
    // 从 src 添加一条到 dest 的边
    struct Node* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// 如果你想让图变成无向图（双向通行），取消下面代码的注释
/*
void addEdgeUndirected(struct Graph* graph, int src, int dest) {
    // src -> dest
    struct Node* newNode = createNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // dest -> src
    newNode = createNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}
*/

4. DFS 的核心逻辑

这是魔法发生的地方。我们使用递归，这使得代码非常简洁直观。

// DFS 递归辅助函数
void DFSUtil(struct Graph* graph, int vertex, bool visited[]) {
    // 1. 标记当前节点为已访问，并打印
    visited[vertex] = true;
    printf("%d ", vertex);

    // 2. 递归访问所有相邻的未访问节点
    struct Node* pCrawl = graph->array[vertex].head;
    while (pCrawl != NULL) {
        int adjVertex = pCrawl->dest;
        if (!visited[adjVertex]) {
            DFSUtil(graph, adjVertex, visited);
        }
        pCrawl = pCrawl->next;
    }
}

// DFS 遍历的主入口函数
void DFS(struct Graph* graph, int startVertex) {
    // 初始化 visited 数组
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i numVertices; i++)
        visited[i] = false;

    // 调用递归辅助函数
    printf("从顶点 %d 开始的深度优先遍历: 
", startVertex);
    DFSUtil(graph, startVertex, visited);
    printf("
");

    free(visited);
}

5. 完整示例与运行

让我们把这些拼起来，看看效果。我们将构建一个包含 4 个节点的有向图。

int main() {
    // 创建一个包含 4 个顶点的图 (0 到 3)
    int V = 4;
    struct Graph* graph = createGraph(V);

    // 添加边构建图结构
    // 这里的逻辑是：2->0, 0->2, 1->2, 0->1, 3->3, 1->3
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 3);

    // 从顶点 2 开始打印 DFS
    DFS(graph, 2);

    return 0;
}

预期输出：

从顶点 2 开始的深度优先遍历: 
2 0 1 3

让我们分析一下这个过程：

  • Start at 2：打印 2。邻居是 0, 3。
  • Go to 0：打印 0。邻居是 1, 2（2 已访问）。
  • Go to 1：打印 1。邻居是 2（已访问），3。
  • Check 3 from 1：3 未访问，Go to 3。打印 3。
  • Backtrack：从 3 回到 1，再到 0，最后回到 2。
  • Check 3 from 2：3 已经被访问过了，跳过。
  • 结束。

深入理解：处理非连通图

上面的代码有一个局限性：如果图是“非连通图”（即有些节点之间根本没有路相连），从单一节点出发的 DFS 无法遍历到所有节点。

想象一下，你有两个互不连通的岛屿。你在一个岛上探险，永远不可能走到另一个岛上去。为了解决这个问题，我们需要修改 DFS 函数，让它能够遍历图中的每一个节点。如果该节点未访问，我们就对它启动一次 DFS。

// 针对非连通图的改进版 DFS
void DFS_Full(struct Graph* graph) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i numVertices; i++)
        visited[i] = false;

    printf("完整的深度优先遍历（含非连通图）: 
");
    for (int i = 0; i numVertices; i++) {
        if (!visited[i]) {
            printf("发现新连通分量，起始节点 %d: ", i);
            DFSUtil(graph, i, visited);
            printf("
");
        }
    }
    free(visited);
}

这个功能对于统计图中存在多少个独立的连通分量非常有用。

迭代式 DFS：使用栈消除递归

虽然递归代码很优雅，但在处理极深的图时，可能会导致栈溢出（Stack Overflow）。作为经验丰富的开发者，我们需要掌握迭代的方法。

迭代式 DFS 显式地使用一个栈来模拟递归调用的过程。

#include  // 为了使用动态数组模拟栈

// 迭代式 DFS 实现
void DFS_Iterative(struct Graph* graph, int startVertex) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i numVertices; i++)
        visited[i] = false;

    // 创建一个栈用于模拟递归
    // 注意：标准 C 没有内置栈库，这里为了简化逻辑，我们仅展示概念
    // 实际工程中可以使用链表或数组实现栈
    int* stack = (int*)malloc(graph->numVertices * sizeof(int));
    int top = -1; // 栈顶指针

    // 初始操作
    stack[++top] = startVertex;

    printf("迭代式 DFS (从 %d 开始): 
", startVertex);

    while (top >= 0) {
        // 弹出栈顶元素
        int currentVertex = stack[top--];

        if (!visited[currentVertex]) {
            printf("%d ", currentVertex);
            visited[currentVertex] = true;
        }

        // 将所有未访问的邻居压入栈中
        // 注意：为了模拟递归的顺序（先左后右），我们需要按特定顺序压栈
        struct Node* pCrawl = graph->array[currentVertex].head;
        
        // 这是一个小技巧：因为栈是后进先出（LIFO），
        // 如果我们希望先处理邻居 A 再处理邻居 B，我们需要先把 B 压栈。
        // 但为了简单起见，这里我们按链表顺序压栈，顺序可能与递归版不同。
        while (pCrawl != NULL) {
            int adjVertex = pCrawl->dest;
            if (!visited[adjVertex]) {
                stack[++top] = adjVertex;
            }
            pCrawl = pCrawl->next;
        }
    }
    printf("
");
    
    free(stack);
    free(visited);
}

算法复杂度分析

这是我们在面试或系统设计时必须考虑的硬指标。

时间复杂度：O(V + E)

  • V (Vertices)：顶点数量。我们初始化 visited 数组需要遍历所有顶点，O(V)。
  • E (Edges)：边数量。在递归或迭代过程中，每条边最多被访问两次（一次是有向图的一次访问，无向图是两次）。所以是 O(E)。
  • 总时间：O(V) + O(E) = O(V + E)。这是非常高效的线性时间复杂度。

空间复杂度：O(V)

  • visited 数组：O(V)。
  • 递归栈 / 显式栈：在最坏情况下（例如一条长链），栈的深度会达到 V，即 O(V)。
  • 邻接表存储：O(V + E)。

常见陷阱与最佳实践

在实际开发中，你可能会遇到以下问题，这里有一些调试建议：

  • 段错误

– 原因：通常是因为忘记分配 INLINECODE90b071d1 数组的内存，或者在 INLINECODEf9f27b8a 中分配内存失败。

– 解决：确保所有的 INLINECODEb8fffc16 都有对应的 INLINECODE32209bb8（尽管在简单的算法题中常省略 INLINECODE17b2b836，但在服务器程序中这是内存泄漏的根源）。检查 INLINECODE1c3dfff4 指针是否初始化为 NULL。

  • 死循环 / 打印重复

– 原因：在 INLINECODE41454a71 函数中，如果你手动构建了双向边，但在 DFS 中忘记检查 INLINECODE51f9b256 数组，程序会陷入环中。

– 解决：严格遵守“检查-访问-标记”的顺序。或者像我代码中写的那样：先检查 !visited 再递归。

  • 性能优化建议

– 位图代替布尔数组：如果你的图非常大（数百万节点），INLINECODE7f1b95af 会占用大量内存。可以使用 INLINECODEb492c69e 或位图来压缩存储。

– 邻接矩阵 vs 邻接表：虽然我们这里使用了邻接表，但如果图是非常稠密的（边数接近顶点数的平方），邻接矩阵（二维数组）在访问速度上可能更快（O(1) 访问任意边），尽管空间复杂度更高。

总结

在这篇文章中，我们全面掌握了图的深度优先搜索（DFS）：

  • 我们了解了 DFS 的核心逻辑——尽可能深地探索，然后回溯。
  • 我们学会了如何在 C 语言中使用邻接表来构建图结构，并处理环的问题。
  • 我们通过递归和迭代两种方式实现了 DFS，理解了它们各自的适用场景。
  • 我们分析了 O(V+E) 的时间复杂度，这是处理图问题的黄金标准之一。

DFS 不仅仅是一个算法，它是解决复杂图论问题（如检测环、拓扑排序、寻找强连通分量）的基石。当你下次面对复杂的网络结构或路径规划问题时，不妨试着用 DFS 的思路去拆解它。

希望这篇指南能帮助你建立起扎实的算法基础。继续练习，尝试修改上面的代码去解决实际问题——你会发现算法世界充满了乐趣！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/53761.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年