对图进行排序以尽可能多地指向箭头

Question

我需要对有向图的节点进行排序，以便向后（与排序顺序相反）的箭头数最少。我可以想到算法（例如，保持交换节点，直到没有交换将改善事物），但我不知道它们运行得有多快，或者他们是否达到最佳解决方案。

这个问题的名称和复杂性是什么？

Answer 1

经过一番思考，我意识到，这个问题可以被一分为二：

1. 确定一个图的最大非循环子图（这is NP-hard）
2. 拓扑排序它（这是a lot easier）

Answer 2

按照深度顺序对节点进行排序可以使用topological sort.完成但是，这只适用于不包含周期的图。你的问题听起来像图中有周期。一种方法是查找周期（请参阅Tortoise and Hare algorithm了解这种方法）并打破周期，记录破坏它的位置。然后对节点进行排序并重新链接。

如果您是为了可视化目的而进行此操作，则会出现一个名为GraphViz的图形渲染库，它执行的操作与您所描述的内容非常相似，然后再布局这些节点。很容易整合和使用，并且会呈现给屏幕或各种不同的输出格式。