排一个图表，使尽可能多的箭头指向作为可能的

Question

我需要节点的一个向图这样，箭头的数量，倒流(针对排序)是最小的。

我能想到的算法(例如保持交换节点，直到没有交换将提高东西)但是我不确定他们如何快速的运行或者他们是否达到最佳的解决方案。

叫什么名字和复杂性，这个问题？

Answer 1

之后有些人认为我意识到，该问题可以分为两种：

1. 确定一个最大的环子的曲线图(它 是NP-硬)
2. 拓扑排序(这是 容易多了)

Answer 2

在深度的顺序排序的节点可以与拓扑排序完成。的。然而，这只能与不包含周期的图表工作。你的问题听起来好像有在图中的循环。一个办法是找到周期（请参见乌龟和野兔算法做的方法此），并打破这个循环，记录在那里你把它弄坏了。然后节点和重新连接进行排序。

如果你这样做了可视化的目的有一些作起来很称为 GraphViz的的图形渲染库类似于你所描述的，然后勾画出的节点。这是很容易集成和使用，并且将渲染到屏幕或多种不同输出格式。