拓扑排序数据结构c语言实现

拓扑排序是一种常用的图算法，用于解决有向无环图（DAG）中的排序问题。其基本思想是通过不断选择入度为0的顶点来构建排序序列。下面是一个基于邻接表的C语言实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define ERROR -1 // 错误标识

// 邻接表结构体
typedef struct EdgeNode {
    int adjvex; // 邻接点编号
    struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;

typedef struct VertexNode {
    int data; // 顶点数据
    EdgeNode *firstEdge; // 指向第一个邻接点的指针
    int indegree; // 顶点的入度
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList adjList; // 邻接表
    int vexNum, edgeNum; // 顶点数和边数
} Graph;

// 初始化图
void initGraph(Graph *G, int vexNum) {
    G->vexNum = vexNum;
    G->edgeNum = 0;
    for (int i = 0; i < vexNum; i++) {
        G->adjList[i].data = i; // 顶点数据
        G->adjList[i].firstEdge = NULL; // 邻接表为空
        G->adjList[i].indegree = 0; // 入度为0
    }
}

// 添加边
void addEdge(Graph *G, int u, int v) {
    EdgeNode *e = (EdgeNode *) malloc(sizeof(EdgeNode));
    e->adjvex = v;
    e->next = G->adjList[u].firstEdge;
    G->adjList[u].firstEdge = e;
    G->adjList[v].indegree++; // 修改入度
    G->edgeNum++; // 边数加1
}

// 拓扑排序
int topSort(Graph *G, int *result) {
    int count = 0; // 计数器
    int front = 0, rear = 0; // 队列的头尾指针
    int queue[MAX_VERTEX_NUM]; // 存储入度为0的顶点
    for (int i = 0; i < G->vexNum; i++) {
        if (G->adjList[i].indegree == 0) {
            queue[rear++] = i; // 入度为0的顶点入队
        }
    }
    while (front != rear) { // 队列非空
        int u = queue[front++]; // 出队一个顶点
        result[count++] = u; // 存储排序结果
        for (EdgeNode *e = G->adjList[u].firstEdge; e != NULL; e = e->next) {
            int v = e->adjvex;
            if (--G->adjList[v].indegree == 0) {
                queue[rear++] = v; // 入度为0的顶点入队
            }
        }
    }
    if (count != G->vexNum) { // 存在环路
        return ERROR;
    }
    return 0;
}

int main() {
    Graph G;
    int vexNum = 6; // 顶点数
    int result[MAX_VERTEX_NUM]; // 存储排序结果
    initGraph(&G, vexNum);
    addEdge(&G, 0, 1);
    addEdge(&G, 0, 2);
    addEdge(&G, 1, 3);
    addEdge(&G, 2, 3);
    addEdge(&G, 2, 4);
    addEdge(&G, 3, 5);
    if (topSort(&G, result) == ERROR) {
        printf("存在环路\n");
    } else {
        printf("拓扑排序结果:\n");
        for (int i = 0; i < vexNum; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
    }
    return 0;
}

以上代码中，`initGraph()`函数用于初始化图，`addEdge()`函数用于添加边，`topSort()`函数用于执行拓扑排序，并将排序结果存储在`result`数组中。在`topSort()`函数中，我们使用队列来存储入度为0的顶点，并依次从队列中取出顶点来构建排序序列。如果排序序列的长度不等于顶点数，则说明存在环路，返回错误标识。否则，将排序序列输出即可。