用c++实现下列问题:【问题描述】给定有向图的adjacent list,写出其拓扑排序结果 【输入形式】节点数目n,和有向图的 adjacent list。每个节点i的adjacent list 表示为数组[i,x,x]; 如第0个顶点和第1,5个有有向边,表示为[0 1 5] 【输出形式】拓扑排序结果 【样例输入】 10 [0 6 1 4] [1 2] [2 7 5] [3 8] [4 5] [5 9] [6 3 2] [7 8] [8 9] [9 ] 【样例输出】[ 0 6 1 4 3 2 7 5 8 9] 【样例说明】 【评分标准】
时间: 2023-10-09 07:12:07 浏览: 110
C++语言实现拓扑排序(含算法介绍和实现原理)
以下是使用 C++ 实现的拓扑排序代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> topologicalSort(int n, vector<vector<int>>& adj_list) {
vector<int> indegree(n, 0); // 存储每个节点的入度
vector<int> result; // 存储排序结果
queue<int> q; // 存储入度为0的节点
// 统计每个节点的入度
for (auto& neighbors : adj_list) {
for (int nei : neighbors) {
indegree[nei]++;
}
}
// 将入度为0的节点加入队列
for (int i = 0; i < n; i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
// 依次取出入度为0的节点进行拓扑排序
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (int nei : adj_list[node]) {
indegree[nei]--;
if (indegree[nei] == 0) {
q.push(nei);
}
}
}
// 判断是否存在环
if (result.size() < n) {
return vector<int>{};
} else {
return result;
}
}
int main() {
int n = 10;
vector<vector<int>> adj_list(n);
adj_list[0] = {6, 1, 4};
adj_list[1] = {2};
adj_list[2] = {7, 5};
adj_list[3] = {8};
adj_list[4] = {5};
adj_list[5] = {9};
adj_list[6] = {3, 2};
adj_list[7] = {8};
adj_list[8] = {9};
adj_list[9] = {};
vector<int> result = topologicalSort(n, adj_list);
for (int node : result) {
cout << node << " ";
}
cout << endl;
return 0;
}
```
输出为 `0 6 1 4 3 2 7 5 8 9`,即为拓扑排序的结果。
阅读全文