C语言DFS与C++ DFS实现有何差异？

“DFS”是一种算法思想，而“C语言DFS”是使用C语言这种编程语言来实现DFS算法的具体代码。

下面我们从几个层面来深入理解。

DFS (Depth-First Search) - 算法思想

DFS,即深度优先搜索，是一种用于遍历或搜索树或图数据结构的算法，它的核心思想非常形象：

“一条路走到黑，走不通了再回头”

想象一下你在迷宫里探险：

1. 你面前有多条路,你选择其中一条（比如最左边的一条）。
2. 沿着这条路一直走下去,每遇到一个新的岔路口，你都选择其中一条继续深入。
3. 如果这条路走不通了（比如是死胡同），或者你已经走过了，你就回溯到上一个岔路口。
4. 然后在上一个岔路口选择下一条你还没走过的路,重复这个过程。
5. 当所有路都走完了,你的探索就结束了。

这个“一条路走到黑”的过程就是“深度优先”，而“走不通了再回头”回溯”。

DFS的核心要素：

1. 访问一个节点：对当前节点进行操作（比如打印它的值）。
2. 标记为已访问：为了避免在后续的遍历中重复访问同一个节点，导致无限循环，必须有一个机制来记录哪些节点已经被访问过。
3. 递归地访问邻居：对于当前节点的每一个未访问过的邻居节点，都递归地执行DFS。

DFS的典型应用场景：

• 在图中查找从一个起点到终点的路径。
• 检测图中是否存在环。
• 拓扑排序。
• 遍历二叉树（前序、中序、后序遍历本质上都是DFS）。

C语言DFS - 具体实现

“C语言DFS”就是将上述抽象的DFS算法思想，用C语言这门编程语言翻译成可以运行的代码，这涉及到C语言的许多特性。

为什么用C语言实现DFS会有一些“特色”？

相比于Python、Java等语言，C语言是手动内存管理和显式类型的语言，这使得它在实现DFS时有一些独特之处，尤其是递归和栈的使用。

C语言实现DFS的两种主要方式：

DFS有两种主要的实现范式,一种是基于递归，另一种是基于栈。

递归实现 (最常见、最简洁)

这是最符合DFS“天然递归”思想的方式，代码通常非常简洁，可读性高。

核心思想： 函数调用自身的机制，天然地维护了一个“调用栈”，这个栈完美地模拟了DFS的“回溯”过程。

代码示例：遍历一个图

假设我们用一个邻接表来表示图。visited数组用来记录节点是否被访问过。

#include <stdio.h>
#include <stdbool.h> // 使用 bool 类型
#define V 5 // 图的顶点数
// 邻接表表示的图结构
struct Graph {
    int adjLists[V][V]; // 简化版，使用邻接矩阵
    // 真正的邻接表会是 struct Node* adjLists[V];
};
// 辅助函数，用于递归DFS
void DFSUtil(int v, bool visited[], int graph[V][V]) {
    // 1. 标记当前节点为已访问，并打印
    visited[v] = true;
    printf("访问节点 %d\n", v);
    // 2. 递归访问所有与当前节点v相邻且未被访问的节点
    for (int i = 0; i < V; ++i) {
        // 如果存在边，并且该邻居节点未被访问
        if (graph[v][i] && !visited[i]) {
            DFSUtil(i, visited, graph);
        }
    }
}
// DFS的包装函数
void DFS(int graph[V][V], int startNode) {
    // 创建一个visited数组并初始化为false
    bool visited[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    // 从起始节点开始递归调用
    printf("从节点 %d 开始DFS遍历:\n", startNode);
    DFSUtil(startNode, visited, graph);
}
int main() {
    // 创建一个图的邻接矩阵表示
    // 0-1, 0-2, 1-3, 2-4
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 0},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0}
    };
    DFS(graph, 0); // 从节点0开始遍历
    return 0;
}

递归实现的优缺点：

• 优点：代码简洁，逻辑清晰，与算法思想高度一致。
• 缺点：可能导致栈溢出，因为每次函数调用都会在调用栈上分配空间，如果图非常深（比如一条长长的链），递归深度会非常大，最终耗尽栈空间。

栈实现 (非递归)

为了避免递归带来的栈溢出风险,我们可以手动模拟递归的过程，也就是使用一个显式的数据结构——栈。

核心思想： 用我们自己的栈来存储待访问的节点，每次从栈顶弹出一个节点进行访问，然后将其所有未访问的邻居按逆序压入栈中（这样可以保证访问顺序与递归版本一致）。

代码示例：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h> // 用于 malloc 和 free
#define V 5
// 定义栈结构
struct Stack {
    int top;
    unsigned capacity;
    int* array;
};
// 创建栈
struct Stack* createStack(unsigned capacity) {
    struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->array = (int*)malloc(stack->capacity * sizeof(int));
    return stack;
}
// 栈是否已满
int isFull(struct Stack* stack) {
    return stack->top == stack->capacity - 1;
}
// 栈是否为空
int isEmpty(struct Stack* stack) {
    return stack->top == -1;
}
// 压栈
void push(struct Stack* stack, int item) {
    if (isFull(stack)) return;
    stack->array[++stack->top] = item;
}
// 弹栈
int pop(struct Stack* stack) {
    if (isEmpty(stack)) return -1; // 错误处理
    return stack->array[stack->top--];
}
// 使用栈的非递归DFS
void DFS_Stack(int graph[V][V], int startNode) {
    bool visited[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    // 创建一个栈并压入起始节点
    struct Stack* stack = createStack(V);
    push(stack, startNode);
    printf("从节点 %d 开始的非递归DFS遍历:\n", startNode);
    while (!isEmpty(stack)) {
        // 弹出栈顶节点
        int v = pop(stack);
        // 如果该节点未被访问
        if (!visited[v]) {
            // 访问它
            visited[v] = true;
            printf("访问节点 %d\n", v);
        }
        // 将所有未访问的邻居压入栈
        // 注意：为了顺序与递归一致，这里需要逆序遍历邻居
        for (int i = V - 1; i >= 0; --i) {
            if (graph[v][i] && !visited[i]) {
                push(stack, i);
            }
        }
    }
    free(stack->array);
    free(stack);
}
int main() {
    int graph[V][V] = {
        {0, 1, 1, 0, 0},
        {1, 0, 0, 1, 0},
        {1, 0, 0, 0, 1},
        {0, 1, 0, 0, 0},
        {0, 0, 1, 0, 0}
    };
    DFS_Stack(graph, 0); // 从节点0开始遍历
    return 0;
}

栈实现的优缺点：

• 优点：避免了递归的栈溢出问题，空间复杂度更可控（堆空间通常比栈空间大得多）。
• 缺点：代码更复杂，需要手动管理栈和数据结构，可读性稍差。

总结与对比

一句话总结：

DFS是“道”，是算法的灵魂；而C语言DFS是“术”，是使用C语言这门工具将灵魂注入肉体，使其能够运行在计算机上的具体方法。 你可以选择递归的“自然之道”，也可以选择手动栈的“控制之术”。