拓扑排序c语言

拓扑排序（Topological Sort）是一种基于有向无环图（DAG）的排序算法，常用于解决任务调度、依赖关系等问题。

以下是拓扑排序的C语言实现示例：

#include <stdio.h>
#define MAXN 1000

int n;  // 顶点个数
int m;  // 边的个数
int cnt[MAXN];  // 每个顶点的入度
int g[MAXN][MAXN];  // 图的邻接矩阵

void topo_sort() {
    int q[MAXN], head = 0, tail = -1;  // 队列
    // 将入度为0的顶点加入队列
    for (int i = 0; i < n; i++) {
        if (cnt[i] == 0) {
            q[++tail] = i;
        }
    }
    // 循环取出队头，更新与之相邻的顶点的入度，
    // 若入度为0，则加入队列
    while (head <= tail) {
        int u = q[head++];
        printf("%d ", u);  // 输出拓扑序列
        for (int v = 0; v < n; v++) {
            if (g[u][v]) {
                cnt[v]--;
                if (cnt[v] == 0) {
                    q[++tail] = v;
                }
            }
        }
    }
}

int main() {
    scanf("%d%d", &n, &m);  // 读入顶点个数和边的个数
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);  // 读入一条边
        g[u][v] = 1;  // 添加边
        cnt[v]++;  // 更新入度
    }
    topo_sort();  // 进行拓扑排序
    return 0;
}

在上述代码中，`n`表示顶点个数，`m`表示边的个数，`cnt`表示每个顶点的入度，`g`表示图的邻接矩阵。`topo_sort`函数实现了拓扑排序的过程。首先将所有入度为0的顶点加入队列。然后循环取出队头，更新与之相邻的顶点的入度，若入度为0，则加入队列。循环直到队列为空。在循环过程中，每次取出的队头即为拓扑序列中的一个顶点，输出即可。

注意，在实现中，为了方便，这里使用了队列来存储入度为0的顶点，而不是用优先队列来维护入度最小的顶点。因为这里没有对边的权值进行处理，所以使用队列并不影响结果。如果需要处理边的权值，则需要使用优先队列，具体实现可以参考其他资料。