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

Question

我正在使用this library对JS中的图执行拓扑排序。问题是，在极少数情况下，图中会包含圈。这些都是结构的次要部分，因此丢弃一些边缘不会对最终结果产生太大影响。然而，当它们出现时，算法就会中断。更新它的最有效方法是什么，这样如果有一两个周期，它就不会崩溃？

Answer 1

根据维基百科：

当且仅当图没有有向圈时，即如果它是有向无环图(

)，拓扑排序是可能的。

因此，如果图中包含循环，则无法找到有效的topsort。我猜您所使用的库在输入图上有一个DAG的要求。因此，算法会因为这一要求而中断。

但是，如果您仍然希望找到一些顶级排序，您可以对图进行以下修改之一: 1)构造图的随机生成树。通过这种方式，您可以将图修改为DAG，并且可以在新图上运行topsort算法。

2)求图的强连通分支(用Tarjan的强连通分支算法)。新图是一个DAG，因此您可以在其上运行topsort算法。

我建议你选择这两个选项，因为至少会有几个JavaScript库具有这些算法(例如，你可以使用一个构建图的最小生成树的库(MST))。通过优化实现，这两种算法都具有线性复杂度。

此外，您还可以运行自己的修改后的DFS算法，该算法会删除找到的每个图周期的一条边。

Answer 2

最小化删除的弧的数量以离开非循环图的问题称为feedback arc set。您链接到的拓扑排序使用的算法会重复查找0度的顶点并将其删除。它离Eades-Lin-Smyth反馈集启发式不远，可以总结如下。如果顶点v的度数为0，则将其移除，在残差图上递归，并将v添加到顺序前面。如果存在出度为0的顶点v，则将其删除，在残差图上递归，并将v附加到顺序上。否则，让v具有最大出度减去入度，删除其所有传入圆弧，然后继续。