当前位置：首页 > 算法 > 正文内容

图论—拓扑排序

亿万年的星光10小时前算法7

前序文章：拓扑排序 - C++目录 - 青少年编程知识记录

一、简述

拓扑排序是针对有向无环图（DAG, Directed Acyclic Graph）的一种排序算法，其核心目标是：将图中所有顶点排成一个线性序列，使得对于图中任意一条有向边 u—>v，顶点 u 都排在顶点 v 的前面。

二、核心概念

1.入度（In-degree）对于顶点 v，入度是指所有以 v 为终点的有向边的数量，记为in_degree[v]。

入度为 0 的顶点，没有前驱节点，可以作为拓扑排序的起点。

2.有向无环图（DAG）拓扑排序的前提条件，如果图中存在环，则无法进行拓扑排序（环内节点互相依赖，无法确定先后顺序）。

三、实现算法

1. 卡恩算法（Kahn's Algorithm）—— 基于入度的贪心算法

核心思想

（1）初始化一个队列，将所有入度为 0 的顶点加入队列。

（2）循环从队列中取出顶点 u，加入拓扑序列，并遍历 u 的所有邻接顶点 v：

将 v 的入度减 1（相当于移除边u——>v) ）。
如果 v 的入度变为 0，则将 v 加入队列。

（3）重复上述步骤，直到队列为空。

（4）若最终拓扑序列的长度等于图中顶点总数，则排序成功；否则图中存在环。

复杂度分析

时间复杂度：O(V + E)，其中 V 是顶点数，E 是边数（每个顶点和边仅被处理一次）。
空间复杂度：O(V)（入度数组、队列、结果数组）。

参考代码

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序：Kahn算法
// 参数：n-顶点数，adj-邻接表，返回拓扑序列（空表示存在环）
vector<int> kahn(int n, vector<vector<int>>& adj) {
    vector<int> in_degree(n, 0); // 记录每个顶点的入度
    vector<int> result;          // 存储拓扑序列
    queue<int> q;                // 存放入度为0的顶点
    // 1. 统计每个顶点的入度
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            in_degree[v]++;
        }
    }
    // 2. 初始化队列：入度为0的顶点入队
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    // 3. 处理队列中的顶点
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u); // 加入拓扑序列
        // 遍历u的邻接顶点，减少入度
        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) { // 入度为0时入队
                q.push(v);
            }
        }
    }
    // 4. 检查是否存在环：若结果长度≠顶点数，说明有环
    if (result.size() != n) {
        return {}; // 空数组表示存在环
    }
    return result; 
}

// 测试样例
int main() {
    int n = 6; // 顶点数（0~5）
    vector<vector<int>> adj(n);
    // 构建有向边：0→1, 0→2, 1→3, 2→3, 3→4, 3→5
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(5);
    vector<int> topo = kahn(n, adj);
    cout<<topo.size()<<endl; 
    if (topo.empty()) {
        cout << "图中存在环，无法拓扑排序！" << endl;
    } else {
        cout << "拓扑序列：";
        for (int v : topo) {
            cout << v << " ";
        }
        // 可能的输出：0 1 2 3 4 5  或  0 2 1 3 5 4 等
    }
    return 0;
}

2. 基于 DFS 的拓扑排序

核心思想

(1)对图进行深度优先搜索（DFS），在访问完一个顶点的所有邻接顶点后，将该顶点加入栈。
(2)所有顶点处理完成后，依次弹出栈顶元素，得到的序列就是拓扑序列。
(3)原理：DFS 会先遍历完顶点的所有后继节点，因此当前顶点可以 “后入栈、先出栈”，满足拓扑顺序。

注意事项

该方法无法直接检测环，需要额外添加一个 onStack 数组标记当前递归栈中的顶点：若在 DFS 中遇到 onStack[v] = true 的顶点，说明存在环。
复杂度与 Kahn 算法相同：O(V + E)。

参考代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// 标记顶点是否被访问，避免重复遍历
vector<bool> visited;
stack<int> stk; // 存储顶点，用于生成拓扑序列

// DFS 遍历函数
void dfs(int u, vector<vector<int>>& adj) {
    visited[u] = true; // 标记当前顶点已访问
    // 遍历u的所有邻接顶点
    for (int v : adj[u]) {
        if (!visited[v]) { // 未访问过的顶点递归DFS
            dfs(v, adj);
        }
    }
    // 所有邻接顶点处理完后，当前顶点入栈
    stk.push(u);
}

// 拓扑排序：基于DFS
vector<int>DFS(int n, vector<vector<int>>& adj) {
    visited.assign(n, false); // 初始化访问标记
    // 遍历所有顶点，处理非连通图的情况
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(i, adj);
        }
    }
    // 栈中元素出栈，得到拓扑序列
    vector<int> result;
    while (!stk.empty()) {
        result.push_back(stk.top());
        stk.pop();
    }
    return result;
}

int main() {
    int n = 6;
    vector<vector<int>> adj(n);
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[3].push_back(5);

    vector<int> topo = DFS(n, adj);
    cout << "拓扑序列（DFS版）：";
    for (int v : topo) {
        cout << v << " ";
    }
    return 0;
}