我正在寻找一种方法来对给定的定向未加权图执行拓扑排序，其中包含循环。结果不仅应包含顶点的排序，还应包含给定排序违反的边集。这组边缘应该是最小的。
由于我的输入图可能很大，我不能使用指数时间算法。如果在多项式时间内无法计算最优解，那么对于给定的问题，启发式算法是否合理？
我正在寻找一种方法来对给定的定向未加权图执行拓扑排序，其中包含循环。结果不仅应包含顶点的排序，还应包含给定排序违反的边集。这组边缘应该是最小的。
由于我的输入图可能很大，我不能使用指数时间算法。如果在多项式时间内无法计算最优解，那么对于给定的问题，启发式算法是否合理？
Eades，Lin和Smyth提议 一种快速有效的反馈电弧设定启发式问题。原始文章是付费墙的背后，但可以免费获得 这里。
有一种拓扑排序算法，通过选择一个没有传入弧的顶点，在图形上减去顶点的递归，并将该顶点预先添加到顺序来构建顶点顺序。 （我正在递归地描述算法，但你不必那样实现它。）Eades-Lin-Smyth算法也可以查找没有传出弧的顶点 追加 他们。当然，可能会发生所有顶点都有传入和传出弧。在这种情况下，选择传入和传出之间具有最高差异的顶点。毫无疑问，这里有实验的空间。
具有可证明的最坏情况行为的算法基于线性编程和图形切割。这些都很整洁，但是保证不太理想（log ^ 2 n或log n log log n倍于所需数量的弧），我怀疑有效的实现将是一个相当大的项目。