c语言实现拓扑排序算法

拓扑排序是一种对有向无环图进行排序的算法，可以用来解决任务调度、依赖关系等问题。以下是用C语言实现拓扑排序的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;             // 该弧所指向的顶点的位置
    struct ArcNode* nextarc; // 指向下一条弧的指针
} ArcNode;

typedef struct VertexNode {
    int data;               // 顶点信息
    int inDegree;           // 入度
    ArcNode* firstarc;       // 指向第一条依附该顶点的弧的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

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

// 初始化邻接表
void InitGraph(ALGraph* G, int vertexNum) {
    G->vexnum = vertexNum;
    G->arcnum = 0;
    for (int i = 0; i < vertexNum; i++) {
        G->vertices[i].data = i;
        G->vertices[i].inDegree = 0;
        G->vertices[i].firstarc = NULL;
    }
}

// 添加一条边<v,w>，即在邻接表中添加一个弧<v,w>，v的出度+1，w的入度+1
void AddArc(ALGraph* G, int v, int w) {
    ArcNode* arc = (ArcNode*)malloc(sizeof(ArcNode));
    arc->adjvex = w;
    arc->nextarc = G->vertices[v].firstarc;
    G->vertices[v].firstarc = arc;
    G->vertices[w].inDegree++;
    G->arcnum++;
}

// 拓扑排序
void TopologicalSort(ALGraph* G) {
    int S[MAX_VERTEX_NUM], top = -1;    // 模拟栈
    int count = 0;                      // 记录输出顶点的个数
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].inDegree == 0) {
            S[++top] = i;               // 将入度为0的顶点入栈
        }
    }
    while (top != -1) {
        int v = S[top--];               // 出栈
        printf("%d ", G->vertices[v].data);
        count++;
        // 遍历v的所有邻接点
        for (ArcNode* arc = G->vertices[v].firstarc; arc != NULL; arc = arc->nextarc) {
            int w = arc->adjvex;
            if (--G->vertices[w].inDegree == 0) {
                S[++top] = w;           // 入度为0则入栈
            }
        }
    }
    if (count < G->vexnum) {
        printf("There is a cycle in the graph.\n");
    }
}

int main() {
    ALGraph G;
    int n, m, v, w;
    printf("Enter the number of vertices and arcs: ");
    scanf("%d%d", &n, &m);
    InitGraph(&G, n);
    printf("Enter the head and tail of each arc:\n");
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &v, &w);
        AddArc(&G, v, w);
    }
    printf("Topological sort result: ");
    TopologicalSort(&G);
    return 0;
}

在这个实现中，我们用邻接表来存储有向图，并在每个顶点中记录它的入度。在拓扑排序过程中，我们首先将所有入度为0的顶点入栈，然后不断出栈并输出，同时将它的邻接点的入度减1，如果减为0则入栈。如果所有顶点都被输出，则拓扑排序成功，否则说明有环存在。