拓扑排序及应用
什么是拓扑排序:
对于一个有向图 G, 如果存在一种结点的序列,使得对于每条边 (u, v), 都有 u 在 v 的前面,则这个顺序叫做拓扑序,给图排拓扑序的过程即是拓扑排序
显然,只有 DAG 才存在拓扑序。
如何进行拓扑排序:
有两种方法:
1.dfs:
dfs 遍历 DAG, 并在遍历完后将结点放在当前序列的首部
—- 代码 —-(来自紫书)
1 | int c[Mn]; |
2.bfs:
运用一个队列,删除在队头的结点, 并寻找入度为 0 的点入队
—- 代码 —-
1 | int topo[Mn]; |
拓扑排序的作用:
首先,拓扑序可以用来定任务的起始时间,这也是一般书上讲的东西
其次,拓扑序可以判定一个有向图是不是 DAG
因为有且只有 DAG 才存在拓扑序
那么,如果将 DAG 的性质和定序结合起来会怎么样?
我们知道,DAG 与 dp 有密不可分的关系
而拓扑序可以给出 DAG 的处理顺序…
也就是说,拓扑序可以给出 DAG 上 dp 的计算顺序
这也是一般 DAG 上 dp 的优化思路