C++的算法：拓扑排序的原理及应用
拓扑排序是对DAG（有向无环图）的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。拓扑排序常用于任务调度、制定课程学习计划等问题中，以确保满足先决条件的任务或课程能够按顺序执行或学习。
拓扑排序的常见算法有Kahn算法和DFS算法。其中，Kahn算法的基本思想是：
1. 从DAG图中选择一个没有前驱（即入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复上述两步，直到当前的DAG图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
以下是一个使用Kahn算法实现拓扑排序的示例，代码如下。
#include <iostream>
#include <vector>
#include <queue>using namespace std;vector<int> topologicalSort(vector<vector<int>>& graph) {int numVertices = graph.size();vector<int> inDegree(numVertices, 0);for (const auto& neighbors : graph) {for (int neighbor : neighbors) {inDegree[neighbor]++;}}queue<int> q;for (int i = 0; i < numVertices; ++i) {if (inDegree[i] == 0) {q.push(i);}}vector<int> sortedOrder;while (!q.empty()) {int u = q.front();q.pop();sortedOrder.push_back(u);for (int v : graph[u]) {if (--inDegree[v] == 0) {q.push(v);}}}if (sortedOrder.size() != numVertices) {sortedOrder.clear(); // 如果存在环，清空结果}return sortedOrder;
}int main() {vector<vector<int>> graph = {{2, 3},{3},{3},{}};vector<int> sortedOrder = topologicalSort(graph);if (!sortedOrder.empty()) {cout << "拓扑排序: ";for (int vertex : sortedOrder) {cout << vertex << " ";}cout << endl;} else {cout << "图形包含循环，无法按拓扑进行排序." << endl;}return 0;
}