【动画讲解】这绝对是2025年最细最易懂的拓扑排序教程，数据结构和算法
同学们，大家好
今天我们一起学习图的应用 拓扑排序
我打个比方，这就好比你在游戏里攒装备
大件装备都得用小件合成，但你先买哪个后买哪个可是有讲究的
比如说要合成兰德里的折磨
你得先购买小面具和魔杖
那小面具又得用红水晶和典籍合成
这时候你会发现，红水晶和典籍
没有依赖于任何前置条件，想买就买
但小面具必须等两个小件都到手后才能合成
那我们购买的时候就必须从没有前置条件的装备先买
比如红水晶、典籍、魔杖这三个
如果我们用图的视角来看，他们三个有什么共同点呢？
没错 他们的入度都为0
这里我们可以选择购买 红水晶
每买完一个装备，合成它的上级装备又少一件
我们把指向上级的边删掉
那么它上级的入度就减少1
这时候我们继续查找入度为0的装备购买
当前入度为0的有典籍和魔杖，我们先购买魔杖
将魔杖的上级的入度-1
这里我们还是不能直接购买大件
因为大件的入度为1，不为0
所以我们继续查找入度为0的装备
目前只有典籍的入度为0
购买典籍，将它的上级入度-1
继续查找入度为0的装备
当前就只有小面具的入度为0，购买小面具
将上级入度-1
最后购买大件
这时候我们的购买顺序就是拓扑排序序列
有意思的是，这个购买顺序并不是唯一的
就像你可以先买增幅典籍再买红水晶，或者先买魔杖
只要保证每次购买的都是入度为0的就行
所以拓扑排序序列并不唯一
要进行拓扑排序，图必须是有向无环图，即DAG图
这里我们加一个环路
这就意味着购买小面具需要先购买增幅
但同时购买增幅又需要先购买小面具这种死循环
那就没法将整个流程推下去了
我们可以先从红宝石购买，剩下入度为0的为魔杖，购买魔杖
继续查找入度为0的顶点，已经没有了
这两个他们的入度都为1，陷入了循环，所以拓扑排序没法继续工作
根据这个特性，拓扑排序可以用来检测 有向图 中是否有环路
好了，我们已经搞清楚了什么是拓扑排序
拓扑排序必须满足有向无环图
以及拓扑排序序列并不是唯一的
有了这些基础，接下来的知识就比较简单了
在前面章节的学习中，我们已经认识了有向无环图
这里我们要引入一个新的概念 AOV 网
AOV网并不涉及什么算法，就是一个简单的概念
AOV网是用有向无环图来表示一个工程
图中的顶点表示一个活动，有向边用来表示每个活动之间的先后顺序
这样的抽象概念我们称之为 AOV网
拓扑排序最重要的作用就是给出一种可行的流程，这个流程可以描述出整个AOV网工程活动的一种流程
立即观看
0