逆拓扑排序算法c语言
时间: 2023-11-25 09:49:08 浏览: 45
以下是逆拓扑排序算法的C语言实现:
```c
#include <stdio.h>
#define MAXVEX 100 // 最大顶点数
typedef struct EdgeNode { // 边表节点
int adjvex; // 邻接点域,存储该顶点对应的下标
struct EdgeNode *next; // 链域,指向下一个邻接点
} EdgeNode;
typedef struct VertexNode { // 顶点表结构
int in; // 顶点入度
int data; // 顶点域,存储顶点信息
EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];
typedef struct { // 图结构
AdjList adjList;
int numVertexes, numEdges; // 图中当前顶点数和边数
} GraphAdjList;
void CreateALGraph(GraphAdjList *G) { // 建立图的邻接表结构
int i, j, k;
EdgeNode *e;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &G->numVertexes, &G->numEdges);
for (i = 0; i < G->numVertexes; i++) { // 输入顶点信息,建立顶点表
printf("请输入第%d个顶点:", i + 1);
scanf("%d", &G->adjList[i].data);
G->adjList[i].in = 0; // 初始化所有顶点入度为0
G->adjList[i].firstedge = NULL; // 初始化所有边表为空
}
for (k = 0; k < G->numEdges; k++) { // 建立边表
printf("请输入边(vi, vj)上的顶点序号:\n");
scanf("%d%d", &i, &j);
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = j;
e->next = G->adjList[i].firstedge;
G->adjList[i].firstedge = e;
G->adjList[j].in++; // 对应顶点入度加1
}
}
void TopologicalSort(GraphAdjList G) { // 拓扑排序
int i, j, k, top = 0;
int *stack; // 存储入度为0的顶点
EdgeNode *e;
stack = (int *)malloc(G.numVertexes * sizeof(int));
for (i = 0; i < G.numVertexes; i++) { // 将所有入度为0的顶点入栈
if (G.adjList[i].in == 0) {
stack[++top] = i;
}
}
while (top != 0) { // 栈不为空
j = stack[top--]; // 出栈一个顶点
printf("%d ", G.adjList[j].data); // 输出该顶点
for (e = G.adjList[j].firstedge; e; e = e->next) { // 将该顶点的所有邻接点入度减1
k = e->adjvex;
if (--G.adjList[k].in == 0) { // 若邻接点入度为0,则入栈
stack[++top] = k;
}
}
}
}
int main() {
GraphAdjList G;
CreateALGraph(&G);
printf("拓扑排序结果为:");
TopologicalSort(G);
printf("\n");
return 0;
}
```