拓扑排序定义
一个有向无环图(DAG) 𝐺=(𝑉,𝐸) 的拓扑排序指它的顶点的一个特殊的线性顺序
它满足:如果边 (𝑢,𝑣)∈𝐸,则顶点 𝑢 一定排在 𝑣 的前面
关键:一个顶点有入边,则说明它有依赖事件需要先执行。
举个例子:
像入度:0 的洗衣服、烧水、买菜,都没有依赖的事件,
换句话说,它们可以直接执行。
像入度:1 的晾衣服、煮咖啡,它们都有 1 个入度,需要
先完成前的事情,若前面事情完成了,代表入度为 0。
拓扑排序步骤
* 1,初始化一个队列。作用:记录入度为0的顶点入队
* 2,遍历整个图,将其中入度为0的顶点入队
* 3,当队列非空,重复以下操作
* * a,取出队首元素,将其插入当前得到的拓扑序列的末端
* * b,遍历它的每条出边,删除,如果对应的终点的入度变为0,则将它入队
* 4,返回得到的拓扑序列
代码模板:(例题)
难度提高的拓扑排序往往需要结合其他算法,例如递推,动态规划等
拓扑排序
1. 可以判断是否有环
2. 可以得到完成若干个任务的拓扑序列