如何忽略拓扑排序中的循环？

Question

我正在使用这个库在JS中对图形执行拓扑排序.问题是在极少数情况下图表将包含周期.这些是结构的一小部分,因此掉落一些边缘不会对最终结果产生很大影响.然而,算法出现时就会中断.更新它的最有效方法是什么,如果有一个或两个循环,它不会崩溃？

Answer 1

根据维基百科:

当且仅当图形没有有向循环时,即,如果它是有向无环图(DAG),则拓扑排序是可能的.

因此,如果图形包含循环,则无法找到有效的topsort.我猜你使用的库要求输入图是一个DAG.因此,算法因该要求而中断.

但是,如果您仍想查找一些topsort,则可以对图形进行以下修改之一:1)构造图形的随机生成树.通过这种方式,您可以将图形修改为DAG,并且可以在新图形上运行topsort算法.

2)找到图的强连通分量(使用Tarjan的强连通分量算法).新图是DAG,因此您可以在其上运行topsort算法.

我建议你这两个选项,因为至少会有几个具有这些算法的JavaScript库(对于1.你可以使用构建图的最小生成树(MST)的库).最佳实现,两种算法都具有线性复杂性.

此外,您可以运行自己的修改后的DFS算法,该算法会删除它找到的每个图形周期的单个边缘.