algorithm - 对图表进行排序以使尽可能多的箭头指向前方

Question

我需要对有向图的节点进行排序，以使向后流动(与排序顺序相反)的箭头数量最少。

我可以想到算法(例如，不断交换节点，直到没有交换会改善事情)但我不确定它们运行的​​速度有多快或者它们是否达到了最佳解决方案。

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

Answer 1

可以使用 topological sort. 来按深度顺序对节点进行排序但是，这仅适用于不包含循环的图形。你的问题听起来像图中有循环。一种选择是找到循环(请参阅 Tortoise and Hare algorithm 了解执行此操作的方法)并打破循环，记录你在哪里打破它。然后对节点进行排序并重新链接。

如果您这样做是为了可视化目的，可以使用一个名为 GraphViz 的图形渲染库。它做的事情与您所描述的非常相似，然后布置节点。它易于集成和使用，可以呈现到屏幕或各种不同的输出格式。