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