拓扑排序详解

1. 什么是拓扑排序？

拓扑排序是对有向无环图（DAG）的顶点进行线性排序，使得：

• 对于任意一条边 u → v，u 在排序中总是位于 v 的前面。

示例应用：

• 课程安排（先修课程在前）

• 任务调度（依赖任务在前）

• 编译顺序（被依赖的库先编译）

---

2. 图解拓扑排序

示例图

     5 → 0 ← 4↓       ↓2 → 3 → 1

1. 图的邻接表表示

0: []
1: []
2: [3]
3: [1]
4: [0, 1]
5: [0, 2]

2. 入度计算

节点 0: 2 (来自 5→0 和 4→0)
节点 1: 2 (来自 4→1 和 3→1)
节点 2: 1 (来自 5→2)
节点 3: 1 (来自 2→3)
节点 4: 0
节点 5: 0

3. 拓扑排序步骤（Kahn算法）

步骤	队列	当前节点	操作	更新后的入度	拓扑序列
1	[4, 5]	-	初始队列（入度=0的节点）	-	-
2	[5]	4	删除 4→0, 4→1	in[0]=1, in[1]=1	[4]
3	[]	5	删除 5→0, 5→2	in[0]=0, in[2]=0	[4,5]
4	[0, 2]	-	0和2入队	-	-
5	[2]	0	0无出边	-	[4,5,0]
6	[]	2	删除 2→3	in[3]=0	[4,5,0,2]
7	[3]	-	3入队	-	-
8	[]	3	删除 3→1	in[1]=0	[4,5,0,2,3]
9	[1]	-	1入队	-	-
10	[]	1	1无出边	-	[4,5,0,2,3,1]

最终拓扑序列：[4, 5, 0, 2, 3, 1]

3.代码

/*拓扑序列对于图中的每一条有向边 (u → v)，节点 u 在排序中总是位于 v 的前面只有无环的有向图才存在拓扑序列（因为环会导致循环依赖，无法排序）有向无环图也叫拓扑图入度：有多少边指向自己出度：有多少边从自己这出去的
*/#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define N 100010int n, m;						//节点数,边数
int h[N],e[N], ne[N], idx;		//图的邻接表存储
int d[N];						//入度数组
int q[N];						//队列(通过数组模拟)//添加有向边a -> b
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}//拓扑排序
bool topsort()
{int hh, tt = -1;	//队列指针(队头，队尾)//初始化队列，将所有入度为0的节点入队for (int i = 1;i <= n;i++){if (!d[i])q[++tt] = i;}while (hh <= tt){int t = q[hh++];	//取出队首顶点//遍历该顶点的所有邻接顶点for (int i = h[t];i != -1;i = ne[i]){int j = e[i];	//邻接顶点jif (--d[j] == 0)	//j的入度减1，若为0则入队q[++tt] = j;}}//判断是否所有顶点都入队过return tt == n - 1;
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof(h));//读入边并构建图while(m--){int a, b;scanf("%d%d", &a, &b);add(a, b);		//b的入度增加d[b]++;}if (!topsort())		//无法拓扑排序(有环)puts("-1");else{//输出拓扑序列for (int i = 0;i < n;i++)printf("%d ", q[i]);puts("");	//puts自动换行}return 0;
}