25.11.6 DAG和拓扑排序

一.DAG即有向无环图，常用于：
任务依赖：某任务必须在另一个任务完成后执行（如编译依赖、任务调度）。
课程顺序：先修课关系。
表达式计算顺序。
动态规划优化：例如在 DAG 上进行最长路径、最短路径 DP。
二.拓扑排序
1.拓扑排序只存在于DAG中
2.两种算法
a.入度法：
(1)统计所有节点的入度
(2)讲所有入度为0的点加入队列
(3)将队头节点出队并加入拓扑序列，将这个点指向的所有点的入度—1(即删除该点的所有出边)
(4)每次出队一个元素后重复(2)(3)操作直到队空
b.dfs法
(1)对一个图进行dfs
(2)当某个节点的子节点全部遍历完了后，将该节点入栈
(3)最后逆序输出栈中节点，即所求的拓扑排序
求拓扑排序时怎么判断是否成环？
入度法：排序完成后判断是否还有节点未排序(代表这些节点的入度永远不为0，即成环)
dfs法：用三个状态的vis数组记录，分别表示未访问(0)，访问中(1)，已访问(2)
一旦递归到某个状态为访问中的节点，就表示成环了(有回边)
三.求最长路径
在DAG求最长路径就是用拓扑排序+dp实现（与求最短路极其相似，区别在dp松弛时的min和max）