对图表进行排序，使尽可能多的箭头指向前方
我需要对有向图的节点进行排序，以使向后流动（与排序顺序相反）的箭头数量最少。
我可以想到算法（例如，继续交换节点，直到没有交换会改善情况），但我不确定它们运行的速度有多快，或者它们是否达到最佳解决方案。
这个问题的名称和复杂性是什么？
I need to sort the nodes of a directed graph such that the number of arrows that flow backwards (against the sorting order) is minimal.
I can think of algorithms (e.g. keep swapping nodes until no swap will improve things) but I'm not sure how fast they run or whether they arrive at the best solution.
What is the name and complexity of this problem?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
按深度顺序对节点进行排序可以使用拓扑排序来完成。但是，这只有效与不包含循环的图。 你的问题听起来像是图中有循环。 一种选择是找到周期（请参阅龟兔赛跑算法，了解一种方法这个）并打破循环，记录你打破它的地方。 然后对节点进行排序并重新链接。
如果您这样做是出于可视化目的，则有一个名为 GraphViz 的图形渲染库，它的功能与您正在描述然后布置节点。 它易于集成和使用，并将渲染到屏幕或各种不同的输出格式。
Sorting nodes in order of depth can be done with a topological sort. However, this will only work with graphs that contain no cycles. Your problem sounds like there are cycles in the graph. One option would be to find the cycles (see the Tortoise and Hare algorithm for a method of doing this) and break the cycle, recording where you broke it. Then sort the nodes and re-link.
If you are doing this for visualisation purposes there is a graph rendering library called GraphViz that does something very similar to what you are describing and then lays out the nodes. It is easy to integrate and use and will render to the screen or a variety of different output formats.
经过一番思考后，我意识到问题可以分为两部分：
After some thought I realized that the problem can be split in two: