用数组表示法做拓朴排序C语言

拓扑排序是一种用于有向无环图（DAG）的排序算法。在DAG中，每个节点代表一个任务，边表示任务间的依赖关系，即若任务A依赖于任务B，则边从B指向A。拓扑排序将DAG中的所有任务排成一个线性序列，使得对于任意一对有依赖关系的任务，其排列顺序都符合依赖关系。

以下是用数组表示法实现拓扑排序的C语言代码：

#include <stdio.h>

#define MAXN 100 // 最大节点数

int n; // 节点数
int G[MAXN][MAXN]; // 邻接矩阵表示有向图
int inDegree[MAXN]; // 记录每个节点的入度
int queue[MAXN]; // 用于拓扑排序的队列
int front, rear; // 队列的头尾指针

void topoSort() {
    int i, j, k;

    // 初始化队列
    front = rear = 0;
    for (i = 0; i < n; i++) {
        if (inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 拓扑排序
    while (front < rear) {
        int u = queue[front++]; // 取出队首节点
        printf("%d ", u); // 输出节点编号
        for (j = 0; j < n; j++) {
            if (G[u][j]) { // 若u->j有一条边
                if (--inDegree[j] == 0) { // j的入度减1
                    queue[rear++] = j; // 若j的入度为0，则入队
                }
            }
        }
    }
    printf("\n");
}

int main() {
    int i, j, u, v;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            G[i][j] = 0; // 初始化邻接矩阵
        }
        inDegree[i] = 0; // 初始化入度数组
    }

    // 读入有向边，构建邻接矩阵
    while (scanf("%d%d", &u, &v) != EOF) {
        G[u][v] = 1;
        inDegree[v]++;
    }

    // 拓扑排序
    topoSort();

    return 0;
}

该代码通过邻接矩阵表示有向图，使用一个数组记录每个节点的入度，使用一个队列进行拓扑排序。在每次排序中，将入度为0的节点加入队列中，然后依次取出队首节点，输出其编号，并将与它相邻的节点的入度减1，若减1后入度为0，则将该节点入队。直到队列为空为止。