请写一段拓普排序的代码并加注释
时间: 2023-05-19 22:02:01 浏览: 193
当然,我可以为您提供拓扑排序的代码和注释,以下是示例代码:
```
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> adj[10001]; // 邻接表存储图
int inDegree[10001]; // 存储每个节点的入度
void topologicalSort(int n) {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i); // 将入度为0的节点加入队列
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出当前节点
for (int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
inDegree[v]--; // 将当前节点的所有邻居节点的入度减1
if (inDegree[v] == 0) {
q.push(v); // 如果邻居节点的入度为0,则加入队列
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入节点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入一条边
adj[u].push_back(v); // 将边加入邻接表
inDegree[v]++; // 将终点的入度加1
}
topologicalSort(n); // 进行拓扑排序
return 0;
}
```
注释如下:
1. 首先定义了一个邻接表 `adj` 和一个数组 `inDegree`,分别用来存储图的邻接关系和每个节点的入度。
2. `topologicalSort` 函数用来进行拓扑排序,接受一个参数 `n` 表示节点数。
3. 在 `topologicalSort` 函数中,首先将所有入度为0的节点加入队列 `q` 中。
4. 然后不断从队列中取出节点,输出该节点,并将该节点的所有邻居节点的入度减1。
5. 如果邻居节点的入度为0,则将其加入队列中。
6. 在 `main` 函数中,首先输入节点数和边数,然后输入每一条边,将其加入邻接表中,并将终点的入度加1。
7. 最后调用 `topologicalSort` 函数进行拓扑排序。
希望这个示例代码和注释能够帮助您理解拓扑排序的实现过程。
阅读全文