拓扑排序(Topological sort)
拓扑排序是对有向无环图(DAG)顶点的一种排序,它使得如果存在u, v的有向路径,那么满足序中u在v前.拓扑排序就是由一种偏序(partical order)得到的一个全序(称为拓扑有序).偏序满足自反性,反对称性,传递性的序.
拓扑排序的思路很简单,就是每次任意找一个入度为0的点输出,并把这个点以及与这个点相关的边删除,实际算法中,用一个队列实现.
算法:
1.把所有入度为0的点入队Q;
2.若队Q非空,则点u出队,输出u,否则转4;
3.把所有与点u相关的边(u,v)删除,若此过程中有点v的的入度变为0,则把v入队Q,转2;
4若出队点数<N,则有环,否则输出结果.
算法复杂度:O(m)
現實生活當中的 DAG
不斷前進、不會後退，有時分化、有時聚合，就是 DAG 的最佳寫照。
是 DAG ：課程擋修規則、族譜、水系、閃電、洗澡。
非 DAG ：道路交通、食物鏈、人體血脈、山脈、氣流。
以時間軸當作主角，緣起緣滅、緣聚緣散，凡事都是 DAG 。