具有最少受侵犯边数的循环图的拓扑排序

Eades，Lin和Smyth提出了一种针对反馈弧集问题的快速有效的启发式方法。原始文章位于付费专区后面，但可以从此处免费获得副本。

有一种用于拓扑排序的算法，可通过选择没有传入弧的顶点，在图上减去该顶点并递归该顶点并将该顶点置于顺序之前来建立顶点顺序。（我递归地描述了该算法，但是您不必那样做。）Eades-
Lin-Smyth算法也查找没有出弧的顶点 并将 其 附加
。当然，所有顶点都有传入和传出弧的情况可能会发生。在这种情况下，请选择传入和传出之间差异最大的顶点。毫无疑问，这里有实验的空间。

具有可证明的最坏情况行为的算法基于线性编程和图割。这些很整洁，但是保证却不理想（log ^ 2 n或log n log log
n所需要的弧数的倍），我怀疑有效的实现将是一个很大的项目。