用队列完成拓扑排序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 indegree; // 顶点入度
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VertexNode;

typedef struct {
    VertexNode vexs[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum; // 顶点数
    int arcnum; // 弧数
} ALGraph;

typedef struct {
    int data[MAX_VERTEX_NUM]; // 存储队列元素的数组
    int front; // 队头指针
    int rear; // 队尾指针
} Queue;

void InitQueue(Queue *Q) { // 初始化队列
    Q->front = Q->rear = 0;
}

int QueueEmpty(Queue *Q) { // 判断队列是否为空
    return Q->front == Q->rear;
}

int EnQueue(Queue *Q, int e) { // 入队
    if ((Q->rear + 1) % MAX_VERTEX_NUM == Q->front) { // 队列已满
        return 0;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAX_VERTEX_NUM;
    return 1;
}

int DeQueue(Queue *Q, int *e) { // 出队
    if (QueueEmpty(Q)) { // 队列为空
        return 0;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_VERTEX_NUM;
    return 1;
}

void CreateALGraph(ALGraph *G) { // 创建有向图
    int i, j, k;
    int v1, v2;
    ArcNode *p;

    printf("请输入有向图的顶点数和弧数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    printf("请输入有向图的顶点：");
    for (i = 0; i < G->vexnum; i++) { // 初始化顶点数组
        scanf("%d", &j);
        G->vexs[i].indegree = 0;
        G->vexs[i].firstarc = NULL;
    }

    printf("请输入有向图的弧(起点 终点)：\n");
    for (k = 0; k < G->arcnum; k++) { // 构造邻接表
        scanf("%d%d", &v1, &v2);
        p = (ArcNode *) malloc(sizeof(ArcNode));
        p->adjvex = v2;
        p->next = G->vexs[v1].firstarc;
        G->vexs[v1].firstarc = p;
        G->vexs[v2].indegree++;
    }
}

void TopologicalSort(ALGraph *G) { // 拓扑排序
    int i, e, count = 0;
    ArcNode *p;
    Queue Q;

    InitQueue(&Q); // 初始化队列

    for (i = 0; i < G->vexnum; i++) { // 将入度为0的顶点入队
        if (G->vexs[i].indegree == 0) {
            EnQueue(&Q, i);
        }
    }

    while (!QueueEmpty(&Q)) { // 队列不为空时
        DeQueue(&Q, &e); // 取出队头元素
        printf("%d ", e); // 输出该顶点
        count++; // 统计已输出的顶点数
        for (p = G->vexs[e].firstarc; p != NULL; p = p->next) { // 将所有以该顶点为起点的弧的终点的入度减1
            if (--G->vexs[p->adjvex].indegree == 0) { // 若终点的入度为0，则入队
                EnQueue(&Q, p->adjvex);
            }
        }
    }

    if (count == G->vexnum) { // 输出顶点数等于图中顶点数，说明拓扑排序成功
        printf("\n拓扑排序成功！\n");
    } else { // 输出顶点数小于图中顶点数，说明存在回路
        printf("\n该有向图存在回路！\n");
    }
}

int main() {
    ALGraph G;

    CreateALGraph(&G);
    TopologicalSort(&G);

    return 0;
}

该代码实现了通过邻接表表示的有向图进行拓扑排序，并使用队列来存储入度为0的顶点。其中，`CreateALGraph`函数用于创建有向图，`TopologicalSort`函数用于进行拓扑排序。在`TopologicalSort`函数中，首先将所有入度为0的顶点入队，然后依次取出队头元素并输出，再将所有以该顶点为起点的弧的终点的入度减1，若该终点的入度为0，则入队。最后，通过统计已输出的顶点数来判断拓扑排序是否成功。如果输出的顶点数等于图中顶点数，则说明拓扑排序成功；否则，说明存在回路，即该有向图不是一个DAG。