拓扑排序

拓扑排序

2025/2/10 10:46:48 来源：https://blog.csdn.net/weixin_40398522/article/details/145534380 浏览: 次关键词：拓扑排序

概述

拓扑排序(Toplogical Sorting) 是一种用于有向无环图(DAG, Directed Acyclic Graph) 的线性排序算法

它将图中的所有节点排成一个线性序列，使得对于图中的每一条有向边(u, v), 节点u在序列中都位于节点v的前面

拓扑排序常用于解决依赖关系问题，例如任务调度、编译顺序

步骤

选择入度为0的节点 : 从图中选择一个入度0的节点(即没有前置依赖的节点)
输出节点: 将该节点添加到排序结果中
删除节点及其边: 从图中删除该节点及其所有出边
重复: 重复上述步骤，直到图中没有节点为止

如果图中存在环，则无法进行拓扑排序

例子分析

假设以下有向无环图 (DAG):

5 → 0 ← 4
↓       ↓
2 → 3 → 1

节点之间的依赖关系为:

5 -> 0
5 -> 2
4 -> 0
4 -> 1
2 -> 3
3 -> 1

拓扑排序的结果可能是: 5、4、2、3、1、0 或 4、5、2、3、1、0

C++ 实现

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 函数：拓扑排序
vector<int> topologicalSort(int numVertices, vector<vector<int>>& adjacencyList) {vector<int> inDegree(numVertices, 0); // 存储每个节点的入度vector<int> result; // 存储拓扑排序的结果// 计算每个节点的入度for (int u = 0; u < numVertices; ++u) {for (int v : adjacencyList[u]) {inDegree[v]++;}}// 使用队列存储入度为0的节点queue<int> q;for (int u = 0; u < numVertices; ++u) {if (inDegree[u] == 0) {q.push(u);}}// 进行拓扑排序while (!q.empty()) {int u = q.front();q.pop();result.push_back(u); // 将当前节点加入结果// 减少相邻节点的入度for (int v : adjacencyList[u]) {inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}}}// 如果结果中的节点数不等于总节点数，说明图中有环if (result.size() != numVertices) {return {}; // 返回空向量表示无法进行拓扑排序}return result;
}int main() {int numVertices = 6;vector<vector<int>> adjacencyList = {{},       // 0{},       // 1{3},      // 2{1},      // 3{0, 1},   // 4{0, 2}    // 5};vector<int> sortedOrder = topologicalSort(numVertices, adjacencyList);if (sortedOrder.empty()) {cout << "图中存在环，无法进行拓扑排序！" << endl;} else {cout << "拓扑排序结果：";for (int u : sortedOrder) {cout << u << " ";}cout << endl;}return 0;
}