帮我写一段c++代码,实现拓扑排序
时间: 2023-03-08 14:02:16 浏览: 202
#include <stdio.h>
#include <stdlib.h>
// 定义最大顶点数
#define MAX_VERTEX_NUM 20
// 定义无穷大
#define INFINITY 65535
// 定义邻接矩阵
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
// 定义一个数组,存储节点的入度
int indegree[MAX_VERTEX_NUM];
// 定义一个数组,存储拓扑排序的结果
int tops[MAX_VERTEX_NUM];
// 初始化邻接矩阵,indegree数组
void Init(int vexnum)
{
int i, j;
// 初始化邻接矩阵
for (i = 0; i < vexnum; i++)
{
for (j = 0; j < vexnum; j++)
{
arc[i][j] = INFINITY;
}
}
// 初始化indegree数组
for (i = 0; i < vexnum; i++)
{
indegree[i] = 0;
}
}
// 拓扑排序
void TopSort(int vexnum)
{
int i, j, k;
int flag;
k = 0;
// 循环处理每个顶点
for (i = 0; i < vexnum; i++)
{
// 找到入度为0的顶点
flag = 0;
for (j = 0; j < vexnum; j++)
{
if (indegree[j] == 0)
{
// 把找到的顶点加入拓扑排序
tops[k++] = j;
// 把此顶点指向的边删除,同时入度减1
indegree[j] = -1;
for (int m = 0; m < vexnum; m++)
{
if (arc[j][m] != INFINITY)
{
indegree[m]--;
}
}
flag = 1;
}
}
// 如果没有找到入度为0的点,则说明此有向图不是一个DAG(有向无环图),拓扑排序失败
if (flag == 0)
{
printf("此有向图不是一个DAG,拓扑排序失败\n");
return;
}
}
// 输出拓扑排序结果
for (i = 0; i < vexnum; i++)
{
printf("%d ", tops[i]);
}
printf("\n");
}
// 主函数
int main()
{
int vexnum;
int start, end;
int i;
// 输入有向图的顶点数
printf("请输入有向图的顶点数:");
scanf("%d", &vexnum);
// 初始化邻接矩阵,indegree数组
Init(vexnum);
// 输入有向图的边
printf("请输入有向图的边(start, end): \n");
for (i = 0; i < vexnum; i++)
{
scanf("%d, %d", &start, &end);
arc[start][end] = 1;
indegree[end]++;
}
// 拓扑排序
TopSort(vexnum);
return 0;
}
阅读全文