拓扑排序

为什么需要拓扑排序

在实际问题中，许多任务之间存在先后依赖关系：选课时需要先修前置课程，编译时需要先编译被依赖的模块，工程施工中某些工序必须在另一些之后才能进行。

拓扑排序就是将这种偏序关系转化为一个全序序列，使得对于每一条有向边 (u, v)，u 在序列中都排在 v 之前。408 考研中，拓扑排序是图这一章的核心考点之一，常以选择题、算法题形式出现。

核心思想

拓扑排序的前提：图必须是有向无环图（DAG, Directed Acyclic Graph）。若图中存在环，则不存在拓扑序列。

核心特点：

AOV 网：用顶点表示活动、有向边表示活动间先后关系的有向图
拓扑序列不唯一：一个 DAG 通常有多个合法的拓扑序列
每次可选入度为 0 的任意顶点：不同的选取顺序产生不同的拓扑序列
拓扑排序可用于判断有向图是否有环

示例 DAG：
  0 → 1 → 3
  ↓       ↑
  2 ------┘

合法拓扑序列：0, 1, 2, 3 或 0, 2, 1, 3

交互可视化

通过下方的交互动画，你可以逐步观察拓扑排序的执行过程：

加载可视化中...

操作详解

BFS 入度法

BFS 入度法（Kahn 算法）是最直观的拓扑排序方法。核心思路：不断选取入度为 0 的顶点输出，并删除该顶点及其出边。

关键步骤：

计算所有顶点的入度
将所有入度为 0 的顶点入队
队列非空时，取出队首顶点并输出
将该顶点的所有邻接顶点入度减 1，若入度变为 0 则入队
重复直到队列为空

// BFS 入度法（Kahn 算法）
// 邻接表存储，n 个顶点
bool TopologicalSort_BFS(int n, int adj[][MAX], int degree[], int indegree[], int result[]) {
    int queue[MAX], front = 0, rear = 0;
    int count = 0;  // 已输出的顶点数

    // 1. 所有入度为 0 的顶点入队
    for (int i = 0; i < n; i++)
        if (indegree[i] == 0)
            queue[rear++] = i;

    // 2. BFS 处理
    while (front < rear) {
        int v = queue[front++];   // 出队
        result[count++] = v;      // 输出

        // 遍历 v 的所有邻接顶点
        for (int j = 0; j < degree[v]; j++) {
            int w = adj[v][j];
            indegree[w]--;        // 入度减 1
            if (indegree[w] == 0)
                queue[rear++] = w; // 入度为 0，入队
        }
    }

    return count == n;  // count < n 说明存在环
}

DFS 逆拓扑序

利用 DFS 的逆后序（reverse post-order） 可以得到拓扑序列。核心思路：对每个未访问顶点执行 DFS，在顶点的所有后继都访问完毕回退时将该顶点压入栈，最终栈顶到栈底即为拓扑序列。

关键步骤：

对每个未访问的顶点调用 DFS
DFS 递归访问所有未访问的邻接顶点
当一个顶点的所有邻接顶点都已访问，将该顶点压栈
所有 DFS 结束后，依次弹栈即为拓扑序列

// DFS 逆拓扑序
int stack[MAX], top = -1;
bool visited[MAX];

void DFS(int v, int adj[][MAX], int degree[]) {
    visited[v] = true;
    for (int j = 0; j < degree[v]; j++) {
        int w = adj[v][j];
        if (!visited[w])
            DFS(w, adj, degree);
    }
    stack[++top] = v;  // 回退时压栈（逆后序）
}

void TopologicalSort_DFS(int n, int adj[][MAX], int degree[]) {
    memset(visited, false, sizeof(visited));
    top = -1;

    for (int i = 0; i < n; i++)
        if (!visited[i])
            DFS(i, adj, degree);

    // 弹栈输出即为拓扑序列
    while (top >= 0)
        printf("%d ", stack[top--]);
}

环的检测

拓扑排序天然可以用于判断有向图是否存在环：

BFS 入度法：若最终输出的顶点数 count < n，则图中存在环。因为环中的顶点入度永远不会减为 0，无法被加入队列。
DFS 法：在 DFS 过程中，若遇到一个正在当前递归路径上的顶点（即处于"访问中"状态），则说明存在环。需要用三种状态标记顶点：

// DFS 检测环（三色标记法）
// 0: 未访问, 1: 访问中（在递归栈上）, 2: 已完成
int color[MAX];

bool HasCycle_DFS(int v, int adj[][MAX], int degree[]) {
    color[v] = 1;  // 标记为访问中
    for (int j = 0; j < degree[v]; j++) {
        int w = adj[v][j];
        if (color[w] == 1) return true;  // 遇到访问中的顶点，存在环
        if (color[w] == 0 && HasCycle_DFS(w, adj, degree))
            return true;
    }
    color[v] = 2;  // 标记为已完成
    return false;
}

复杂度分析

算法	时间复杂度	空间复杂度	说明
BFS 入度法	O(V + E)	O(V)	每个顶点入队/出队一次，每条边处理一次
DFS 逆拓扑序	O(V + E)	O(V)	每个顶点、每条边各访问一次，递归栈深度最大 V

其中 V 为顶点数，E 为边数。两种方法时间复杂度相同，BFS 入度法更适合判断是否有环。

考研高频考点

⭐ 给定 DAG，写出所有可能的拓扑序列（选择题高频）
⭐ BFS 入度法的执行过程模拟（手动模拟入度变化、队列状态）
⭐ 拓扑排序判断有向图是否有环（概念题/选择题必考）
⭐ 拓扑序列不唯一的条件（队列中同时存在多个入度为 0 的顶点）
DFS 逆后序与拓扑序列的关系（偶尔考）
AOV 网的定义及与 AOE 网的区别（简答题/选择题）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

拓扑排序 ​

为什么需要拓扑排序 ​

核心思想 ​

交互可视化 ​

操作详解 ​

BFS 入度法 ​

DFS 逆拓扑序 ​

环的检测 ​

复杂度分析 ​

考研高频考点 ​

相关文章