拓扑排序：原理、实现与分析

什么是拓扑排序？

拓扑排序是针对有向无环图（DAG） 的一种顶点排序算法。简单来说，它能把图中的所有顶点排成一个线性序列，使得对于图中任意一条有向边 u→v，顶点 u 一定出现在 v 之前。

举个例子：在大学课程安排中，“数据结构” 是 “算法设计” 的先修课（有一条边 数据结构→算法设计），那么拓扑排序的结果里，“数据结构” 必须排在 “算法设计” 前面。

如果图中存在环（比如 a→b→c→a），就不可能有这样的序列，因此拓扑排序也常用于检测图中是否有环。

适合的图存储方式

拓扑排序的核心操作是 “遍历某个顶点的所有邻接顶点”，因此邻接表是最适合的存储方式，原因有二：

效率高：邻接表通过链表直接存储顶点的邻接关系，遍历一个顶点的所有邻接顶点只需要访问对应链表，总耗时与边数成正比。
省空间：对于稀疏图（边数远少于顶点数的平方），邻接表比邻接矩阵（需要用二维数组存储所有可能的边）更节省内存。

基础版实现（C 语言）

核心思路

计算每个顶点的入度（指向该顶点的边的数量）。
用队列收集所有入度为 0 的顶点（这些顶点没有前置依赖，可先输出）。
从队列中取出顶点，加入拓扑序列；再将其邻接顶点的入度减 1，若某邻接顶点入度变为 0，加入队列。
若最终拓扑序列的长度等于顶点总数，排序成功；否则图中存在环。

代码实现

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

#define MAX_VEX 10  // 顶点数上限

// 邻接表节点
typedef struct ArcNode {
    int adjvex;               // 邻接顶点下标
    struct ArcNode* nextarc;  // 下一个邻接顶点
} ArcNode;

// 顶点节点
typedef struct VNode {
    char data;       // 顶点数据
    ArcNode* firstarc;  // 邻接表头指针
} VNode, AdjList[MAX_VEX];

// 图结构
typedef struct {
    AdjList vertices;  // 邻接表数组
    int vexnum;        // 顶点数
    int arcnum;        // 边数
    int inDegree[MAX_VEX];  // 入度数组
} ALGraph;

// 初始化固定图（修复入度初始化问题）
void initFixedGraph(ALGraph* G) {
    // 1. 初始化顶点数和边数
    G->vexnum = 5;  // A(0), B(1), C(2), D(3), E(4)
    G->arcnum = 5;

    // 2. 初始化顶点数据和入度（关键：先将所有入度设为0）
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].data = 'A' + i;  // A、B、C、D、E
        G->vertices[i].firstarc = NULL;
        G->inDegree[i] = 0;  // 入度初始化为0（修复核心）
    }

    // 3. 添加边并更新入度（边：A→B, A→C, B→D, C→D, D→E）
    // 边A→B（0→1）
    ArcNode* p1 = (ArcNode*)malloc(sizeof(ArcNode));
    p1->adjvex = 1;
    p1->nextarc = G->vertices[0].firstarc;
    G->vertices[0].firstarc = p1;
    G->inDegree[1]++;  // B的入度+1

    // 边A→C（0→2）
    ArcNode* p2 = (ArcNode*)malloc(sizeof(ArcNode));
    p2->adjvex = 2;
    p2->nextarc = G->vertices[0].firstarc;
    G->vertices[0].firstarc = p2;
    G->inDegree[2]++;  // C的入度+1

    // 边B→D（1→3）
    ArcNode* p3 = (ArcNode*)malloc(sizeof(ArcNode));
    p3->adjvex = 3;
    p3->nextarc = G->vertices[1].firstarc;
    G->vertices[1].firstarc = p3;
    G->inDegree[3]++;  // D的入度+1

    // 边C→D（2→3）
    ArcNode* p4 = (ArcNode*)malloc(sizeof(ArcNode));
    p4->adjvex = 3;
    p4->nextarc = G->vertices[2].firstarc;
    G->vertices[2].firstarc = p4;
    G->inDegree[3]++;  // D的入度再+1（总2）

    // 边D→E（3→4）
    ArcNode* p5 = (ArcNode*)malloc(sizeof(ArcNode));
    p5->adjvex = 4;
    p5->nextarc = G->vertices[3].firstarc;
    G->vertices[3].firstarc = p5;
    G->inDegree[4]++;  // E的入度+1
}

// 打印图结构
void printGraph(ALGraph* G) {
    printf("=== 图结构 ===\n");
    printf("顶点数：%d（", G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        printf("%c", G->vertices[i].data);
        if (i != G->vexnum - 1) printf(", ");
    }
    printf("）\n");

    printf("边数：%d\n", G->arcnum);
    printf("边列表（u→v）：\n");
    for (int i = 0; i < G->vexnum; i++) {
        ArcNode* p = G->vertices[i].firstarc;
        while (p != NULL) {
            printf("  %c→%c\n", G->vertices[i].data, G->vertices[p->adjvex].data);
            p = p->nextarc;
        }
    }

    printf("每个顶点的入度：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("  %c: %d\n", G->vertices[i].data, G->inDegree[i]);
    }
    printf("==============\n\n");
}

int topologicalSort(ALGraph* G) {
    int queue[MAX_VEX];      // 队列用于存储入度为0的顶点
    int front = 0, rear = 0; // 队列头尾指针
    int topo[MAX_VEX];       // 存储拓扑排序结果
    int count = 0;           // 记录已排序的顶点数

    // 初始化：将所有入度为0的顶点入队
    for (int i = 0; i < G->vexnum; i++) {
        if (G->inDegree[i] == 0) {
            queue[rear++] = i;
        }
    }

    // 主循环：处理队列中的顶点
    while (front < rear) {
        int u = queue[front++];  // 取出队首顶点
        topo[count++] = u;       // 加入拓扑序列

        // 遍历顶点u的所有邻接点
        ArcNode* p = G->vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            G->inDegree[v]--;    // 邻接点入度减1

            // 如果入度减为0，则加入队列
            if (G->inDegree[v] == 0) {
                queue[rear++] = v;
            }
            p = p->nextarc;      // 处理下一个邻接点
        }
    }

    // 检查是否存在环：排序顶点数不等于总顶点数说明有环
    if (count != G->vexnum) {
        printf("图中存在环，无法拓扑排序！\n");
        return 0;  // 排序失败
    }

    // 输出拓扑排序结果
    printf("拓扑排序结果：");
    for (int i = 0; i < count; i++) {
        printf("%c ", G->vertices[topo[i]].data);
    }
    printf("\n");
    return 1;  // 排序成功
}

int main() {
    ALGraph G;
    initFixedGraph(&G);
    printGraph(&G);
    topologicalSort(&G);
    return 0;
}

时空复杂度分析

时间复杂度：O(n + e)

其中 n 是顶点数，e 是边数。

理由：初始化入度和队列需 O(n)；每个顶点入队 / 出队一次（O(n)）；每条边被遍历一次（O(e)），总耗时为两者之和。
空间复杂度：O(n + e)

理由：邻接表存储需 O(n + e)（顶点数组 O(n) + 边链表 O(e)）；入度数组、队列、拓扑序列数组共需 O(n)，总空间为两者之和。

核心算法代码示例

bool TopologicalSort(Graph G){
    InitStack(S);        //初始化栈，存储入度为0的顶点
    int count = 0;       //计数，记录当前已输出的顶点数
    // 遍历所有顶点，将入度为0的顶点入栈
    for(int i = 0; i < G.vexnum; ++i){
        if(indegree[i] == 0){
            Push(S, i);  //入度为0的顶点入栈
        }
    }

    while(!IsEmpty(S)){
        int i;
        Pop(S, i);       //栈顶顶点出栈
        count++;

        // 遍历顶点i的所有邻接顶点
        for(Arc *p = G.vex[i].firstarc; p; p = p->nextarc){
            int v = p->adjvex;  //获取i指向的邻接顶点
            --indegree[v];      //邻接顶点的入度减1
            if(indegree[v] == 0){
                Push(S, v);     //入度减为0的顶点入栈
            }
        }
    }

    // 若输出顶点数小于总顶点数，说明图中存在回路
    if(count < G.vexnum){
        return false;
    } else {
        return true;  //拓扑排序成功
    }
}

目录CONTENT

拓扑排序