對圖進行排序以儘可能多地指向箭頭

Question

我需要對有向圖的節點進行排序，以便向後（與排序順序相反）的箭頭數最少。我可以想到算法（例如，保持交換節點，直到沒有交換將改善事物），但我不知道它們運行得有多快，或者他們是否達到最佳解決方案。

這個問題的名稱和複雜性是什麼？

Answer 1

經過一番思考，我意識到，這個問題可以被一分爲二：

1. 確定一個圖的最大非循環子圖（這is NP-hard）
2. 拓撲排序它（這是a lot easier）

Answer 2

按照深度順序對節點進行排序可以使用topological sort.完成但是，這隻適用於不包含週期的圖。你的問題聽起來像圖中有周期。一種方法是查找週期（請參閱Tortoise and Hare algorithm瞭解這種方法）並打破週期，記錄破壞它的位置。然後對節點進行排序並重新鏈接。

如果您是爲了可視化目的而進行此操作，則會出現一個名爲GraphViz的圖形渲染庫，它執行的操作與您所描述的內容非常相似，然後再佈局這些節點。很容易整合和使用，並且會呈現給屏幕或各種不同的輸出格式。