c语言队列实现拓扑排序

拓扑排序是一种基于有向无环图（DAG）的排序算法，它将图中的节点按照一定的规则排序，使得所有的有向边从排在前面的节点指向排在后面的节点。在拓扑排序中，入度为 0 的节点可以先被处理，因为它们没有任何依赖关系，而出度为 0 的节点则不能先处理，因为它们依赖于其他节点。

下面是一个基于 C 语言队列实现拓扑排序的代码：

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

#define MAXVEX 100  // 最大顶点数

typedef struct EdgeNode {  // 边表节点
    int adjvex;  // 邻接点域，存储该顶点的下标
    int weight;  // 权值
    struct EdgeNode *next;  // 链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode {  // 顶点表结构体
    int in;  // 顶点入度
    char data;  // 顶点数据
    EdgeNode *firstedge;  // 边表头指针
} VertexNode, AdjList[MAXVEX];

typedef struct {  // 队列结构体
    int data[MAXVEX];
    int front, rear;
} Queue;

void InitQueue(Queue *Q);  // 初始化队列
void EnQueue(Queue *Q, int x);  // 入队
int DeQueue(Queue *Q);  // 出队
int TopologicalSort(AdjList G, int n);  // 拓扑排序

int main() {
    AdjList G;
    int n, m, i, j, k;

    printf("请输入顶点数和边数：");
    scanf("%d%d", &n, &m);

    for (i = 0; i < n; i++) {  // 初始化顶点表
        G[i].in = 0;
        G[i].data = 'A' + i;
        G[i].firstedge = NULL;
    }

    for (k = 0; k < m; k++) {  // 建立边表
        printf("请输入边（Vi,Vj）的顶点序号：");
        scanf("%d%d", &i, &j);

        EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G[i].firstedge;
        G[i].firstedge = e;
        G[j].in++;  // 统计入度
    }

    TopologicalSort(G, n);  // 拓扑排序

    return 0;
}

void InitQueue(Queue *Q) {
    Q->front = 0;
    Q->rear = 0;
}

void EnQueue(Queue *Q, int x) {
    Q->data[Q->rear++] = x;
}

int DeQueue(Queue *Q) {
    return Q->data[Q->front++];
}

int TopologicalSort(AdjList G, int n) {
    int i, j, k;
    Queue Q;
    InitQueue(&Q);

    for (i = 0; i < n; i++) {
        if (G[i].in == 0) {  // 入度为 0 的顶点入队
            EnQueue(&Q, i);
        }
    }

    while (Q.front != Q.rear) {
        int v = DeQueue(&Q);
        printf("%c ", G[v].data);  // 输出拓扑排序结果

        EdgeNode *e = G[v].firstedge;  // 访问此顶点的所有邻接点
        while (e != NULL) {
            if (--G[e->adjvex].in == 0) {  // 将入度为 0 的邻接点入队
                EnQueue(&Q, e->adjvex);
            }
            e = e->next;
        }
    }

    return 0;
}

在代码中，我们首先定义了边表节点和顶点表结构体，然后根据用户输入的顶点数和边数，建立起图的边表和顶点表。在拓扑排序中，我们需要统计每个顶点的入度，并将入度为 0 的顶点加入队列中。然后依次访问队列中的顶点，输出拓扑排序结果，并将其邻接点的入度减 1，如果邻接点的入度为 0，则将其加入队列中。最后我们可以得到图的拓扑排序结果。