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

Question

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

Answer 1

根据维基百科：

当且仅当图没有有向环，即，如果它是有向无环图 (DAG)，拓扑排序是可能的。

因此，如果图形包含循环，则无法找到有效的 topsort。我猜您使用的库要求输入图是 DAG。因此，该算法由于该要求而中断。

但是，如果您仍然想找到一些顶级排序，您可以对图进行以下修改之一： 1）构造图的随机生成树。这样，您可以将图修改为 DAG，并且可以在新图上运行 topsort 算法。

2）找到图的强连通分量（用Tarjan的强连通分量算法）。新图是一个 DAG，因此您可以在其上运行 topsort 算法。

我建议您使用这两个选项，因为至少会有几个 JavaScript 库具有这些算法（对于 1。您可以使用构建图 (MST) 的最小生成树的库）。优化实现，两种算法都具有线性复杂度。

此外，您可以运行自己修改过的 DFS 算法，该算法会删除它找到的每个图循环的一条边。

Answer 2

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