在最近的算法过程中，我们必须形成一个缩合图，并计算其自反传递闭包以获得一个偏序。但从来没有人真正解释过为什么我们要在图表中这样做我理解缩合图的要点，因为它突出了强连通的成分，但是偏序给了我们什么，原来的图没有？
实现的算法如下：
查找强连接组件（我使用了Tarjan算法）
为SCC创建缩合图
邻接矩阵的形式自反传递闭包（WARVER算法）
这样做就形成了部分顺序，但是找到部分订单能给我们带来什么好处？
最佳答案
与其他任何数据结构或算法一样，只有在需要其属性时才有优势：-）
您所描述的过程的结果是可以用来（轻松）回答以下问题的结构：
对于两个节点x, y。它是x<=y和/或y<=x还是两者都不是？
对于节点x，查找所有a或a<=x的节点？
这些性质可以用来回答关于初始图（DAG）的其他问题。例如，如果添加edgex<=a将产生一个循环。可通过交叉集x->y、ofA和seta<=x进行检查。如果B交集y<=b不为空，则edgeA将创建一个循环。
结构还可以用于更简单的实现算法，这些算法使用图来描述其他依赖项例如，B表示计算结果x->y用于计算x->y。如果计算x比所有计算y都更改，则应重新计算x或将其标记为“脏”或从缓存中删除a的结果。