C++怎么实现拓扑排序算法_C++图论与有向无环图(DAG)应用

拓扑排序适用于有向无环图，通过Kahn算法或DFS实现，用于确定节点线性序列以满足依赖关系，如课程安排或任务调度。

拓扑排序是图论中针对有向无环图（DAG）的一种线性排序算法，它能将图中的所有顶点排成一个序列，使得对于每一条有向边 (u, v)，u 在序列中都出现在 v 的前面。C++ 中实现拓扑排序主要有两种方法：基于深度优先搜索（DFS）和基于入度的 Kahn 算法。

1. 什么是拓扑排序？

拓扑排序只适用于有向无环图（DAG）。如果图中存在环，则无法进行拓扑排序，因为会出现逻辑矛盾（比如 A 必须在 B 前，B 又必须在 A 前）。

典型应用场景包括：

课程学习顺序安排
工程任务调度
编译依赖处理

2. 使用 Kahn 算法（基于入度）

Kahn 算法是一种广度优先的思想，通过不断移除入度为 0 的节点来构建拓扑序列。

步骤如下：

计算每个节点的入度
将所有入度为 0 的节点加入队列
从队列中取出节点，加入结果序列，并将其邻居的入度减 1
若某邻居入度变为 0，则加入队列
重复直到队列为空

#include 
#include 
#include 
using namespace std;

vector topologicalSort(int n, vector>& adj) {
    vector indegree(n, 0);
    
    // 计算每个节点的入度
    for (int u = 0; u < n; u++) {
        for (int v : adj[u]) {
            indegree[v]++;
        }
    }

    queue q;
    // 将入度为 0 的节点入队
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    vector topo;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo.push_back(u);

        // 遍历 u 的邻居，减少其入度
        for (int v : adj[u]) {
            indegree[v]--;
            if (indegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 若结果长度不等于节点数，说明存在环
    if (topo.size() != n) {
        return {}; // 返回空表示无法拓扑排序
    }

    return topo;
}

3. 使用 DFS 实现拓扑排序

DFS 方法通过后序遍历的方式记录节点，然后逆序输出即为拓扑序列。

需要维护三个状态：

未访问（0）
正在访问（1，用于检测环）
已完成（2）

vector topo;
vector visited;

bool dfs(int u, vector>& adj) {
    if (visited[u] == 1) return false; // 存在环
    if (visited[u] == 2) return true;  // 已完成

    visited[u] = 1;
    for (int v : adj[u]) {
        if (!dfs(v, adj)) return false;
    }
    visited[u] = 2;
    topo.push_back(u); // 后序添加
    return true;
}

vector topologicalSortDFS(int n, vector>& adj) {
    visited.assign(n, 0);
    topo.clear();

    for (int i = 0; i < n; i++) {
        if (visited[i] == 0) {
            if (!dfs(i, adj)) {
                return {}; // 存在环
            }
        }
    }

    reverse(topo.begin(), topo.end());
    return topo;
}

4. 完整示例与测试

以下是一个完整可运行的例子：

int main() {
    int n = 6;
    vector> adj(n);

    // 构建图：0→1, 0→2, 1→3, 2→3, 3→4, 4→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[4].push_back(5);

    vector result = topologicalSort(n, adj);

    if (result.empty()) {
        cout << "图中存在环，无法进行拓扑排序。\n";
    } else {
        cout << "拓扑排序结果：";
        for (int x : result) {
            cout << x << " ";
        }
        cout << endl;
    }

    return 0;
}

输出结果应为：0 1 2 3 4 5，符合依赖关系。

基本上就这些。Kahn 算法更直观，适合初学者；DFS 方法更贴近递归思维，也便于检测环。根据实际需求选择即可。注意建图方式（邻接表）和边界处理，拓扑排序就能稳定运行。

# c++ # ai # ios # stream # 排序算法 # 递归 # 算法 # 图中 # 遍历 # 适用于 # 是一个 # 是一种 # 就能 # 出现在 # 两种 # 能将

返回目录在线咨询

上一篇：docker中编译nodejs并使用nginx启动
下一篇：构建高效多商家商城系统的策略与实践

您的项目需求