C语言 拓扑排序代码
时间: 2023-11-29 21:44:42 浏览: 164
以下是C语言实现拓扑排序的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode { // 边结点
int adjvex; // 邻接点在数组中的位置下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点结点
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
int indegree; // 顶点的入度
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} Graph;
// 创建图
void CreateGraph(Graph *G) {
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入%d个顶点的数据:", G->vexnum);
for (int i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
G->vertices[i].indegree = 0;
}
printf("请输入%d条边的信息:\n", G->arcnum);
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
printf("请输入第%d条边的起点和终点:", i + 1);
scanf("%d%d", &v1, &v2);
ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
arc->adjvex = v2 - 1;
arc->nextarc = G->vertices[v1 - 1].firstarc;
G->vertices[v1 - 1].firstarc = arc;
G->vertices[v2 - 1].indegree++;
}
}
// 拓扑排序
void TopologicalSort(Graph G) {
int count = 0; // 计数器,记录已经输出的顶点数
int *stack = (int *)malloc(G.vexnum * sizeof(int)); // 栈,存放入度为0的顶点
int top = -1; // 栈顶指针
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].indegree == 0) { // 将入度为0的顶点入栈
stack[++top] = i;
}
}
while (top != -1) { // 栈不为空时循环
int v = stack[top--]; // 出栈一个顶点
printf("%d ", G.vertices[v].data); // 输出该顶点
count++;
for (ArcNode *arc = G.vertices[v].firstarc; arc != NULL; arc = arc->nextarc) {
int w = arc->adjvex;
if (--G.vertices[w].indegree == 0) { // 将入度为0的顶点入栈
stack[++top] = w;
}
}
}
if (count < G.vexnum) { // 输出的顶点数小于总顶点数,说明有环
printf("该图有环\n");
}
}
int main() {
Graph G;
CreateGraph(&G);
printf("拓扑排序结果为:");
TopologicalSort(G);
return 0;
}
```
阅读全文