一、递归与图：拓扑排序的递归实现（基于DFS）

拓扑排序，说白了就是给有向无环图（DAG）排个序。你想想看，在项目开发中，模块A依赖模块B，模块B又依赖模块C——那编译顺序肯定是C→B→A。这就是拓扑排序的典型场景。

我个人习惯用DFS来实现拓扑排序。为什么？因为递归的思维更贴近图的遍历本质。你沿着一条路径走到黑，发现走不动了（没有出边了），那就把当前节点记录下来——这不就是后序遍历吗？

1.1 拓扑排序的核心思想

拓扑排序的目标是：对于图中的每条有向边 u→v，在排序结果中，u 必须出现在 v 之前。说白了，就是保证依赖关系不被打破。

我记得刚入行时，有个同事用BFS（Kahn算法）实现拓扑排序，代码写得挺漂亮。但我问他：「如果图里有环，你怎么检测？」他愣了一下。嗯，DFS实现拓扑排序有个天然优势——环检测是顺带完成的。

1.2 算法流程与状态机

我们给每个节点定义三种状态：

状态值	含义	说明
0	未访问	还没碰过这个节点
1	访问中	正在递归处理该节点（在递归栈中）
2	已访问	该节点及其所有后继都已处理完毕

为什么会用到「访问中」这个状态？因为环检测就靠它。如果你在DFS过程中，遇到一个状态为1的节点——说明你走回头路了，有环！

1.3 代码实现

下面是我常用的实现模板。注意看状态数组的用法：

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

#define MAX_NODES 100

// 邻接表节点
typedef struct AdjListNode {
    int dest;
    struct AdjListNode* next;
} AdjListNode;

// 图结构
typedef struct Graph {
    int numNodes;
    AdjListNode** head;
} Graph;

// 创建图
Graph* createGraph(int n) {
    Graph* g = (Graph*)malloc(sizeof(Graph));
    g->numNodes = n;
    g->head = (AdjListNode**)malloc(n * sizeof(AdjListNode*));
    for (int i = 0; i < n; i++)
        g->head[i] = NULL;
    return g;
}

// 添加有向边 u -> v
void addEdge(Graph* g, int u, int v) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = v;
    newNode->next = g->head[u];
    g->head[u] = newNode;
}

// DFS递归函数
// state: 0=未访问, 1=访问中, 2=已访问
// result: 存储拓扑排序结果（逆序）
// idx: 当前结果数组的写入位置
int dfs(Graph* g, int node, int* state, int* result, int* idx) {
    // 标记为「访问中」
    state[node] = 1;

    // 遍历所有邻接节点
    AdjListNode* cur = g->head[node];
    while (cur != NULL) {
        int neighbor = cur->dest;

        if (state[neighbor] == 1) {
            // 遇到「访问中」的节点 → 有环！
            return 0;  // 失败
        }

        if (state[neighbor] == 0) {
            // 递归处理未访问的邻居
            if (!dfs(g, neighbor, state, result, idx))
                return 0;  // 下层检测到环，向上传播
        }

        cur = cur->next;
    }

    // 所有后继处理完毕，标记为「已访问」
    state[node] = 2;
    // 后序位置记录节点
    result[(*idx)++] = node;
    return 1;  // 成功
}

// 拓扑排序主函数
// 返回1表示成功，0表示有环
int topologicalSort(Graph* g, int* result) {
    int n = g->numNodes;
    int* state = (int*)calloc(n, sizeof(int));  // 初始全0
    int idx = 0;

    // 对每个未访问节点启动DFS
    for (int i = 0; i < n; i++) {
        if (state[i] == 0) {
            if (!dfs(g, i, state, result, &idx)) {
                free(state);
                return 0;  // 检测到环
            }
        }
    }

    free(state);
    // 此时result中存储的是逆序，需要反转
    for (int i = 0; i < idx / 2; i++) {
        int temp = result[i];
        result[i] = result[idx - 1 - i];
        result[idx - 1 - i] = temp;
    }
    return 1;
}

// 测试
int main() {
    Graph* g = createGraph(6);
    addEdge(g, 5, 2);
    addEdge(g, 5, 0);
    addEdge(g, 4, 0);
    addEdge(g, 4, 1);
    addEdge(g, 2, 3);
    addEdge(g, 3, 1);

    int result[MAX_NODES];
    if (topologicalSort(g, result)) {
        printf("拓扑排序结果: ");
        for (int i = 0; i < g->numNodes; i++)
            printf("%d ", result[i]);
        printf("\n");
    } else {
        printf("图中存在环，无法进行拓扑排序\n");
    }

    return 0;
}

1.4 核心逻辑流程图

下面这张图展示了DFS拓扑排序的完整流程。我建议你仔细看看「状态1→状态2」的转换时机——这是理解递归拓扑排序的关键：

1.5 避坑指南与实战经验

我在项目中用DFS拓扑排序踩过不少坑，这里分享几个最典型的：

• 递归深度问题：如果图有几千个节点，递归深度可能超过栈限制。我建议在递归函数开头加一个深度参数，超过阈值（比如1000）就报错退出。
• 结果反转别忘：很多新手第一次写DFS拓扑排序，直接返回递归顺序——结果完全反了。记住，后序遍历的结果要反转才是拓扑序。
• 多起点问题：图可能不连通，所以主函数里要遍历所有节点。我见过有人只从一个节点开始DFS，结果漏掉了一大片。

1.6 复杂度分析

指标	值	说明
时间复杂度	O(V + E)	每个节点和每条边恰好访问一次
空间复杂度	O(V)	状态数组 + 递归栈（最坏情况）
环检测	O(1) 额外	通过状态1即可判断，无需额外数据结构

你想想看，O(V+E)的复杂度，对于大多数实际场景已经够用了。我处理过最大的图有10万个节点、50万条边，DFS拓扑排序跑下来也就几百毫秒。当然，如果递归深度太大，可以考虑用显式栈模拟递归——但那就是另一回事了。

嗯，DFS拓扑排序的核心就这些。记住三态标记、后序遍历、结果反转——这三个要点抓住了，代码写起来就很顺。下次遇到依赖解析、任务调度这类问题，不妨试试这个思路。

---

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