c语言拓扑排序

拓扑排序是一种对有向无环图进行排序的算法，用于解决依赖关系的问题。在C语言中，可以使用邻接表来表示有向图，然后利用队列实现拓扑排序。以下是C语言实现拓扑排序的示例代码：

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode {
    int adjvex;
    struct ArcNode *next;
} ArcNode;

typedef struct VertexNode {
    int data;
    ArcNode *first;
} VertexNode;

VertexNode G[MAX_VERTEX_NUM];
int indegree[MAX_VERTEX_NUM];

void TopologicalSort(int n) {
    int i, j, k, cnt = 0;
    ArcNode *p;
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    for (i = 0; i < n; i++) {
        if (indegree[i] == 0)
            queue[rear++] = i;
    }
    while (front != rear) {
        j = queue[front++];
        printf("%d ", G[j].data);
        cnt++;
        for (p = G[j].first; p; p = p->next) {
            k = p->adjvex;
            indegree[k]--;
            if (indegree[k] == 0)
                queue[rear++] = k;
        }
    }
    if (cnt != n)
        printf("Graph has a cycle\n");
}

int main() {
    int n, m, i, j, k;
    ArcNode *p;
    scanf("%d%d", &n, &m);
    for (i = 0; i < n; i++) {
        G[i].data = i;
        G[i].first = NULL;
        indegree[i] = 0;
    }
    for (i = 0; i < m; i++) {
        scanf("%d%d", &j, &k);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = k;
        p->next = G[j].first;
        G[j].first = p;
        indegree[k]++;
    }
    TopologicalSort(n);
    return 0;
}

在这个示例代码中，我们使用了邻接表来存储有向图，并且使用了一个数组来记录每个顶点的入度。在拓扑排序过程中，我们首先将所有入度为0的顶点加入队列中，然后依次处理队列中的每个顶点，将其邻接点的入度减1，如果邻接点的入度为0，则将其加入队列中。最后，如果输出的顶点个数不等于总顶点数，则说明图中存在环。