拓扑排序：原理、实现与分析
什么是拓扑排序？
拓扑排序是针对有向无环图（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];
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;
ArcNode* p = G->vertices[u].firstarc;
while (p != NULL) {
int v = p->adjvex;
G->inDegree[v]--;
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)，总空间为两者之和。
评论区