拓扑排序

拓扑排序(Topological Sorting)由一个有向无环图(Directed Acyclic Graph (DAG))的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序

1.每个顶点出现且只出现一次

2.若A在序列中排在B的前面,则在图中不存在从B到A的路径

卡恩算法

卡恩于1962年提出的算法。简单来说就是,假设L是存放结果的列表,先找到那些入度为零的节点,把这些节点放到L中,因为这些节点没有任何的父节点。然后把与这些节点相连的边从图中去掉,再寻找图中的入度为零的节点。对于新找到的这些入度为零的节点来说,他们的父节点已经都在L中了,所以也可以放入L。重复上述操作,直到找不到入度为零的节点。如果此时L中的元素个数和节点总数相同,说明排序完成;如果L中的元素个数和节点总数不同,说明原图中存在环,无法进行拓扑排序


选择入度为0的顶点(1,7),这里选择 1,去掉1和它的边


继续选择入度为0的顶点(2,7),这里选择 2,去掉2和它的边


继续选择入度为0的顶点(5,7),这里选择 5,去掉5和它的边


继续选择入度为0的顶点(6,7),这里选择 7,去掉7和它的边


继续选择入度为0的顶点(6,4),这里选择 4,去掉4和它的边


继续选择入度为0的顶点(6,3),这里选择 3,去掉3和它的边


此时6 和 8放在最后面即可

最终排序结果为 1 2 5 7 4 3 6 8

从这里我们可以看出,拓扑排序可以有多种不同的解


参考:

维基-拓扑排序

上一篇: 并查集-校验图是否有回路
下一篇: 字符串搜索算法
作者邮箱: 203328517@qq.com