写一段拓普排序的C++代码并加注释
时间: 2023-05-24 20:06:26 浏览: 96
拓扑排序C++代码
// 拓扑排序算法实现
#include <stdio.h>
#include <stdlib.h>
#define N 100 // 定义数据量的最大值
int G[N][N]; // 存储图的邻接矩阵
int indegree[N]; // 存储节点入度的数组
int n, m; // n表示节点个数,m表示边个数
void topsort() {
int i, j, k;
int queue[N]; // 存储入度为0的节点的队列
int front = 0, rear = -1; // 定义队首和队尾指针
for(i = 0; i < n; ++i) {
if(indegree[i] == 0) { // 如果节点i的入度为0
queue[++rear] = i; // 将节点i加入队列末尾
}
}
while(front <= rear) { // 如果队列非空,则进行下列操作
k = queue[front++]; // 取出队首节点k
printf("%d ", k); // 打印节点k
for(j = 0; j < n; ++j) {
if(G[k][j] == 1) { // 如果存在边(i,j)
--indegree[j]; // 将节点j的入度减1
if(indegree[j] == 0) { // 如果节点j入度变为0
queue[++rear] = j; // 将节点j加入队列末尾
}
}
}
}
}
int main() {
int i, j;
scanf("%d%d", &n, &m); // 输入节点个数和边个数
for(i = 0; i < m; ++i) { // 输入每条边的起点和终点
int u, v;
scanf("%d%d", &u, &v);
G[u][v] = 1;
++indegree[v];
}
printf("拓扑排序:");
topsort(); // 进行拓扑排序
printf("\n");
return 0;
}
阅读全文