16、递归与图：深度优先搜索（DFS）的递归实现

图这种数据结构，说实话，很多初学者会觉得它比树要「野」一些。树有明确的父子关系，图呢？节点之间可以任意连接，甚至形成环。那怎么遍历它？

深度优先搜索（DFS）就是最经典的方法之一。而用递归来实现 DFS，我个人认为是理解图遍历最优雅的方式——代码短，逻辑清晰，几乎就是「走到黑，再回头」的直译。

16.1 图的表示：邻接表

在写 DFS 之前，得先搞定图的存储。我习惯用邻接表，原因很简单：稀疏图下内存省，遍历邻居也快。

邻接表本质上是一个数组，每个元素是一个链表（或动态数组），记录该节点的所有邻居。

// 邻接表节点
typedef struct AdjNode {
    int vertex;
    struct AdjNode* next;
} AdjNode;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjNode** adjLists;
    int* visited;  // 访问标记
} Graph;

你看，结构就这么简单。adjLists[i] 就是节点 i 的邻居链表头。visited 数组用来标记哪些节点已经访问过——这是防止死循环的关键。

16.2 递归 DFS 的核心逻辑

DFS 的递归实现，说白了就三步：

1. 标记当前节点已访问
2. 处理当前节点（比如打印、记录路径）
3. 对每个未访问的邻居，递归调用 DFS

为什么能递归？因为每个邻居的遍历过程和当前节点完全一样。这就是递归的「自相似性」。

void DFS(Graph* graph, int startVertex) {
    // 标记已访问
    graph->visited[startVertex] = 1;
    printf("访问节点: %d\n", startVertex);

    // 遍历所有邻居
    AdjNode* temp = graph->adjLists[startVertex];
    while (temp != NULL) {
        int neighbor = temp->vertex;
        if (!graph->visited[neighbor]) {
            DFS(graph, neighbor);  // 递归！
        }
        temp = temp->next;
    }
}

嗯，这里要注意：递归调用之前一定要检查 visited 状态。我曾经见过一个同事，忘了这个检查，结果在环形图上无限递归，栈溢出崩了。排查了半天才发现是少了个 if。

16.3 图解递归过程

光说可能不够直观，我画了一张图，展示从节点 0 出发的 DFS 递归调用过程。

从图中可以看到，DFS 先沿着 0→1→2→3 一路走到头，然后回溯到 2，发现还有邻居 4 没访问，再去访问 4。访问完 4 之后，再回溯到 2，然后回溯到 1，最后回到 0。整个过程就是「一条路走到黑，走不通了再回头」。这就是深度优先这个名字的由来。

16.4 完整示例：从节点0开始遍历

下面是一个完整的可运行示例。我创建了一个 5 个节点的图，连接关系就是上面那张图的样子。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 邻接表节点
typedef struct AdjNode {
    int vertex;
    struct AdjNode* next;
} AdjNode;

// 图结构
typedef struct Graph {
    int numVertices;
    AdjNode** adjLists;
    int* visited;
} Graph;

// 创建节点
AdjNode* createNode(int v) {
    AdjNode* newNode = (AdjNode*)malloc(sizeof(AdjNode));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (AdjNode**)malloc(vertices * sizeof(AdjNode*));
    graph->visited = (int*)malloc(vertices * sizeof(int));
    
    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}

// 添加边（无向图）
void addEdge(Graph* graph, int src, int dest) {
    // src -> dest
    AdjNode* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    
    // dest -> src（无向图需要双向添加）
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 递归 DFS
void DFS(Graph* graph, int vertex) {
    graph->visited[vertex] = 1;
    printf("访问节点: %d\n", vertex);
    
    AdjNode* temp = graph->adjLists[vertex];
    while (temp != NULL) {
        int neighbor = temp->vertex;
        if (!graph->visited[neighbor]) {
            DFS(graph, neighbor);
        }
        temp = temp->next;
    }
}

int main() {
    Graph* graph = createGraph(5);
    
    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    
    printf("DFS 从节点0开始:\n");
    DFS(graph, 0);
    
    return 0;
}

运行结果：

DFS 从节点0开始:
访问节点: 0
访问节点: 1
访问节点: 2
访问节点: 3
访问节点: 4

16.5 避坑指南：递归 DFS 的常见问题

我在项目中用递归 DFS 踩过不少坑，挑几个典型的说说：

• 栈溢出：图太大（比如几万个节点连成一条线），递归深度太深，栈就爆了。我曾经在一个嵌入式项目里，递归深度到了 5000 层，直接段错误。后来改成迭代版 DFS 才解决。
• 忘记标记 visited：这个前面提过。环形图下不标记 visited，递归就停不下来。轻则死循环，重则栈溢出。
• 邻接表顺序影响遍历顺序：同一个图，如果邻居插入顺序不同，DFS 的访问顺序也会不同。这不是 bug，但如果你依赖遍历顺序做逻辑判断，就要小心了。

16.6 递归 DFS 的应用场景

说实话，递归 DFS 在实际项目中用得非常多。我简单列几个：

场景	说明
连通分量检测	从每个未访问节点出发做 DFS，能找出图中有几个连通块
拓扑排序	对有向无环图做 DFS，按完成时间逆序输出就是拓扑序
迷宫求解	把迷宫看成图，DFS 就是「沿着墙走」的探索策略
检测环	DFS 过程中如果遇到已访问的邻居（且不是父节点），说明有环

你想想看，这些场景本质上都是在做同一件事：沿着一条路径尽可能深地探索，直到无路可走再回头。递归恰好完美匹配这个逻辑。

16.7 小结

递归 DFS 是图算法中最基础也最优雅的实现方式。代码量少，逻辑直观，非常适合用来理解图的遍历思想。但也要记住它的局限性——递归深度受限于系统栈。小图用递归，大图用迭代，这是我个人的经验法则。

嗯，这一章就到这里。代码不多，但背后的思想值得多琢磨。下次遇到图遍历的问题，不妨先想想：能不能用递归 DFS 解决？

---

公众号：蓝海资料掘金营，微信 deep3321