图的拓扑排序
拓扑排序是一种对有向无环图(Directed Acyclic Graph, DAG)进行排序的算法。在拓扑排序中，我们将图中的节点按照一定的顺序进行排序，使得对于图中的每一条有向边 (u, v) ，u 在排序中都出现在 v 之前。
拓扑排序的思想是通过不断删除入度为0的节点，直到所有节点都被删除或者剩下的节点都有入度大于0，从而得到一个拓扑排序的序列。
下面是使用C++实现拓扑排序的代码示例：
#include <iostream>
#include <vector>
#include <queue>using namespace std;vector<int> topologicalSort(vector<vector<int>>& graph) {int n = graph.size();vector<int> inDegree(n, 0); // 记录每个节点的入度vector<int> result; // 用于存储排序后的结果// 统计每个节点的入度for (int i = 0; i < n; i++) {for (int j = 0; j < graph[i].size(); j++) {inDegree[graph[i][j]]++;}}queue<int> q;// 将入度为0的节点加入队列for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}// 拓扑排序while (!q.empty()) {int node = q.front();q.pop();result.push_back(node);// 更新与当前节点相邻节点的入度for (int i = 0; i < graph[node].size(); i++) {int neighbor = graph[node][i];inDegree[neighbor]--;if (inDegree[neighbor] == 0) {q.push(neighbor);}}}// 检查是否有环if (result.size() != n) {cout << "Graph contains a cycle!" << endl;return vector<int>();}return result;
}int main() {int n; // 节点个数int m; // 有向边的个数cout << "Enter the number of nodes: ";cin >> n;cout << "Enter the number of directed edges: ";cin >> m;vector<vector<int>> graph(n); // 定义有向图的邻接表表示cout << "Enter the directed edges: " << endl;for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;graph[u].push_back(v);}vector<int> result = topologicalSort(graph);cout << "Topological sort: ";for (int i = 0; i < result.size(); i++) {cout << result[i] << " ";}return 0;
}
在上面的代码中，我们首先输入了有向图的节点个数和有向边的个数。然后，我们通过邻接表的形式输入了有向边的信息。接下来，我们调用了 topologicalSort 函数对图进行拓扑排序，并将排序结果输出。