我需要对有向图的节点进行排序，以使向后流动的箭头数量（与排序顺序相反）最小。
我可以想到算法（例如，不断交换节点，直到没有交换可以改善事情）但我不确定它们运行的速度或它们是否达到最佳解决方案。
这个问题的名称和复杂性是什么？
问问题
500 次
2 回答
2
可以使用拓扑排序来按深度顺序对节点进行排序。 但是，这仅适用于不包含循环的图。您的问题听起来像是图中有循环。一种选择是找到循环（有关执行此操作的方法，请参见Tortoise and Hare 算法）并打破循环，记录你打破它的位置。然后对节点进行排序并重新链接。
如果您出于可视化目的这样做，则有一个名为GraphViz的图形渲染库，它的功能与您所描述的非常相似，然后布置节点。它易于集成和使用，并将呈现到屏幕或各种不同的输出格式。
于 2009-04-21T08:18:11.760 回答