题解 | #【模板】拓扑排序#纯C实现

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。
2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

因此，在数据输入时，不仅要存储节点和边，还要存储点的入度。

在代码中，实现一个链表数组，存储节点和出发点是改节点的边，数组下标对应节点；声明一个int型二维数组存储节点的入度。

判断图是否有拓扑排序的思路如下：

1. 从 DAG 图中选择一个 没有前驱（即入度为0）的顶点并输出。
2. 从图中删除该顶点和所有以它为起点的有向边。
3. 重复 1 和 2 直到当前的 DAG 图为空或当前图中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。

那么在代码实现中，主要方法如下：

1. 初始化：声明一个队列queue，存储所有入度为0的节点，count存储出队节点数，输出数组out存储出队结果。
2. 循环判断：当queue不为空，出队一个节点，count++，删除该节点的所有边，并将边指向节点的入度-1，若入度=0，将该节点加入队。
3. 结束判断：如果count等于节点总数，则存在拓扑排序，输出out；如果count不等于节点总数，则不存在拓扑排序。

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

typedef struct line{//存储指向节点，表示一条边
    int to;
    struct line* next;
} LINE;

int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    LINE* points=(LINE*)malloc((n+1)*sizeof(LINE));//点数组，下标表示点，链表存储指向的所有边
    int* inDegree=(int*)calloc(n+1, sizeof(int));//存储每个点的入度
    int* out=(int*)calloc(n, sizeof(int));//存储输出结果
    for (int i=1; i<=n; i++) {
        points[i].next=NULL;
    }
    int from,to;
    LINE* p=NULL;
    LINE** p_tail=(LINE**)calloc((n+1),sizeof(LINE*));//链表尾指针数组
    for(int i=1;i<=n;i++){//p_tail初始化
        p_tail[i]=&points[i];
    }
    for (int i=0; i<m; i++) {//points初始化
        scanf("%d %d",&from,&to);
        p=(LINE *)malloc(sizeof(LINE));
        p->to=to;
        p->next=NULL;
        //连接在末尾
        p_tail[from]->next=p;
        p_tail[from]=p_tail[from]->next;
        inDegree[to]++;
    }

    //队列初始化
    int queue_size=n+1;
    int* queue=(int*)calloc(queue_size, sizeof(int));
    int head=0,tail=0;
    for(int i=1;i<=n;i++){
        if(inDegree[i]==0){
            queue[tail]=i;
            tail=(tail+1)%queue_size;
            inDegree[i]=-1;//标记已经入队过了
        }
    }

    //BFS
    int count=0;
    while (head!=tail) {
        //出队
        int point=queue[head];
        head=(head+1)%queue_size;
        //存储结果并且计数加一
        out[count]=point;
        count++;

        //删除point的所有边
        while (points[point].next!=NULL) {
            inDegree[points[point].next->to]--;
            if(inDegree[points[point].next->to]==0){//减后若为0，直接入队
                queue[tail]=points[point].next->to;
                tail=(tail+1)%queue_size;
                inDegree[points[point].next->to]=-1;//标记已经入队过了
            }
            p=points[point].next;
            points[point].next=points[point].next->next;
            free(p);  
        }
        
    }

    if(count!=n){
        printf("-1\n");
    }else {
        printf("%d",out[0]);
        for(int i=1;i<count;i++){
            printf(" %d",out[i]);
        }
    }

    free(points);
    free(inDegree);
    free(out);
    free(p_tail);
    return 0;
}