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; // 边表头指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct { // 图
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 顶点数和弧数
} ALGraph;

int *etv, *ltv; // 事件最早发生时间和最迟发生时间
int *stack; // 存储拓扑序列的栈
int top = -1; // 栈顶指针

int *indegree; // 存储各个顶点的入度

void CreateGraph(ALGraph *G) { // 创建AOV网
    int i, j, k;
    ArcNode *p;
    printf("请输入顶点数和弧数：");
    scanf("%d,%d", &G->vexnum, &G->arcnum);
    for (i = 0; i < G->vexnum; i++) { // 初始化邻接表
        G->vertices[i].data = i;
        G->vertices[i].firstarc = NULL;
    }
    for (k = 0; k < G->arcnum; k++) { // 建立邻接表
        printf("请输入弧头和弧尾：");
        scanf("%d,%d", &i, &j);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

void TopologicalSort(ALGraph *G) { // 拓扑排序
    int i, k, gettop;
    ArcNode *p;
    int count = 0; // 计数，记录当前已经输出的顶点数
    top = -1; // 初始化栈
    etv = (int *)malloc(G->vexnum * sizeof(int)); // 事件最早发生时间
    for (i = 0; i < G->vexnum; i++) {
        etv[i] = 0; // 初始化为0
    }
    stack = (int *)malloc(G->vexnum * sizeof(int)); // 存储拓扑序列的栈
    indegree = (int *)malloc(G->vexnum * sizeof(int)); // 存储各个顶点的入度
    for (i = 0; i < G->vexnum; i++) { // 初始化各个顶点的入度
        indegree[i] = 0;
    }
    for (i = 0; i < G->vexnum; i++) { // 计算各个顶点的入度
        for (p = G->vertices[i].firstarc; p; p = p->nextarc) {
            indegree[p->adjvex]++;
        }
    }
    for (i = 0; i < G->vexnum; i++) { // 将入度为0的顶点入栈
        if (indegree[i] == 0) {
            stack[++top] = i;
        }
    }
    while (top > -1) { // 栈不为空
        gettop = stack[top--]; // 出栈
        printf("%d -> ", gettop); // 输出拓扑序列
        count++; // 计数
        for (p = G->vertices[gettop].firstarc; p; p = p->nextarc) { // 对gettop的每个邻接点的入度减1
            k = p->adjvex;
            if (--indegree[k] == 0) { // 若入度减为0，则入栈
                stack[++top] = k;
            }
            if (etv[gettop] + 1 > etv[k]) { // 更新各个事件最早发生时间
                etv[k] = etv[gettop] + 1;
            }
        }
    }
    if (count < G->vexnum) { // 拓扑序列中顶点数小于G->vexnum，说明存在环
        printf("Error: Graph has a cycle\n");
        exit(0);
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    TopologicalSort(&G);
    return 0;
}