深入理解C语言深度优先搜索（DFS）

DFS 的应用场景

• 图的连通性检测
• 拓扑排序
• 寻找路径或迷宫求解
• 检测图中是否存在环

C语言实现DFS（递归方式）

下面我们使用C语言图遍历中最常见的邻接矩阵来表示图，并通过递归实现DFS。

#include <stdio.h>#define MAX_VERTICES 100int graph[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵int visited[MAX_VERTICES];               // 访问标记数组int n;                                   // 顶点数量void dfs(int vertex) {    visited[vertex] = 1;  // 标记为已访问    printf("%d ", vertex);    // 遍历所有可能的邻接点    for (int i = 0; i < n; i++) {        if (graph[vertex][i] == 1 && !visited[i]) {            dfs(i);  // 递归访问未访问的邻接点        }    }}int main() {    // 示例：构建一个简单的图    n = 5;    // 初始化邻接矩阵（无向图）    graph[0][1] = graph[1][0] = 1;    graph[0][2] = graph[2][0] = 1;    graph[1][3] = graph[3][1] = 1;    graph[2][4] = graph[4][2] = 1;    // 初始化访问数组    for (int i = 0; i < n; i++) {        visited[i] = 0;    }    printf("DFS遍历顺序: ");    dfs(0);  // 从顶点0开始DFS    printf("\n");    return 0;}

代码解析

上述代码展示了如何使用C语言深度优先搜索遍历一个无向图：

1. graph 是一个二维数组，用于表示图的邻接关系。
2. visited 数组记录每个顶点是否被访问过，避免重复访问。
3. dfs() 函数是核心，它先标记当前节点为已访问，然后递归访问所有未访问的邻接节点。

注意事项

• DFS 使用递归时，要注意栈溢出问题（尤其在大型图中）。
• 对于有向图，只需调整邻接矩阵的赋值方式即可。
• 如果图不连通，需要在外层循环中对每个未访问节点调用 DFS。

总结

通过本教程，你应该已经掌握了 DFS算法 的基本原理和 C 语言实现方法。无论是解决迷宫问题、判断图的连通性，还是进行拓扑排序，DFS 都是一个强大而灵活的工具。多加练习，你将能轻松应对各种图论相关的问题！

继续探索 C语言图遍历 的世界，让算法成为你的超能力！