c++ 拓扑排序
概念
拓扑排序是一种线性排序算法，主要用于有向无环图 (DAG, Directed Acyclic Graph) 中，对顶点进行排序，使得对于每一条边 u→v，顶点 u 都排在顶点 v之前。
特点
-
适用于有向无环图。
-
拓扑排序的结果不唯一（如果有多种线性排序方式满足条件）。
-
常用于任务调度、依赖关系解析、课程安排等场景。
算法
基于 Kahn 算法 (入度法)
- 核心思想：依次找出入度为 0 的节点，移除它们以及相关边，直到图中没有节点。
- 步骤：
- 统计所有节点的入度。
- 将入度为 0 的节点入队。
- 每次从队列中取出一个节点，加入结果序列，并将它指向的节点入度减 1。
- 如果入度变为 0，则加入队列。
- 直到队列为空，若结果序列包含所有节点，则排序成功。
基于深度优先搜索 (DFS)
- 核心思想：对每个节点进行深度优先搜索，节点访问完成后，逆序加入结果。
- 步骤：
- 用一个数组记录节点是否被访问。
- 对每个未访问的节点进行 DFS。
- 每次访问完成一个节点后，将其压入栈中。
- 最后将栈中元素依次弹出，得到排序结果。
实例
使用 Kahn 算法（c++）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序函数
vector<int> topologicalSortKahn(int n, vector<vector<int>>& adj) {
vector<int> inDegree(n, 0); // 记录每个节点的入度
for (auto& edges : adj) {
for (int v : edges) {
inDegree[v]++;
}
}
queue<int> q; // 存放入度为 0 的节点
for (int i = 0; i < n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
vector<int> result;
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u); // 加入结果
for (int v : adj[u]) { // 移除节点 u 的所有边
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
if (result.size() != n) {
throw runtime_error("Graph has a cycle!"); // 图中存在环
}
return result;
}
// 主函数
int main() {
int n = 6; // 节点数
vector<vector<int>> adj = {
{2, 3}, // 节点 0 指向 2, 3
{3, 4}, // 节点 1 指向 3, 4
{}, // 节点 2 无指向
{5}, // 节点 3 指向 5
{5}, // 节点 4 指向 5
{} // 节点 5 无指向
};
try {
vector<int> result = topologicalSortKahn(n, adj);
cout << "拓扑排序结果: ";
for (int v : result) {
cout << v << " ";
}
} catch (const exception& e) {
cout << e.what() << endl;
}
return 0;
}
使用 DFS 方法（c++）
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// 深度优先搜索
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& stk) {
visited[node] = true;
for (int v : adj[node]) {
if (!visited[v]) {
dfs(v, adj, visited, stk);
}
}
stk.push(node); // 当前节点访问完成后入栈
}
// 拓扑排序函数
vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {
vector<bool> visited(n, false);
stack<int> stk;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i, adj, visited, stk);
}
}
vector<int> result;
while (!stk.empty()) {
result.push_back(stk.top());
stk.pop();
}
return result;
}
// 主函数
int main() {
int n = 6; // 节点数
vector<vector<int>> adj = {
{2, 3}, // 节点 0 指向 2, 3
{3, 4}, // 节点 1 指向 3, 4
{}, // 节点 2 无指向
{5}, // 节点 3 指向 5
{5}, // 节点 4 指向 5
{} // 节点 5 无指向
};
vector<int> result = topologicalSortDFS(n, adj);
cout << "拓扑排序结果: ";
for (int v : result) {
cout << v << " ";
}
return 0;
}
课程表安排问题
我们有 nnn 门课程，编号为 0,1,…,n−1。有一些课程的先修要求，比如修读课程 1之前必须修读课程 0。这些要求可以表示为一个有向图，判断是否可以完成所有课程，并给出一个可行的学习顺序。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// 拓扑排序函数 (基于 Kahn 算法)
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<vector<int>> adj(numCourses); // 邻接表
vector<int> inDegree(numCourses, 0); // 入度数组
// 构建图和入度
for (auto& prereq : prerequisites) {
adj[prereq.second].push_back(prereq.first);
inDegree[prereq.first]++;
}
queue<int> q; // 存放入度为 0 的节点
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
vector<int> result; // 存储拓扑排序结果
while (!q.empty()) {
int course = q.front();
q.pop();
result.push_back(course);
for (int next : adj[course]) {
inDegree[next]--;
if (inDegree[next] == 0) {
q.push(next);
}
}
}
// 如果结果中包含所有课程，返回排序；否则返回空
return (result.size() == numCourses) ? result : vector<int>();
}
// 主函数
int main() {
int numCourses = 6; // 总课程数
vector<pair<int, int>> prerequisites = {
{1, 0}, {2, 1}, {3, 1}, {4, 2}, {5, 3}, {5, 4}
};
vector<int> order = findOrder(numCourses, prerequisites);
if (order.empty()) {
cout << "无法完成所有课程（存在环）！" << endl;
} else {
cout << "课程学习顺序: ";
for (int course : order) {
cout << course << " ";
}
cout << endl;
}
return 0;
}