如何將無向圖轉換爲無週期有向圖（定向無環圖）

Question

我有一個無向圖，我希望將其轉換爲有向圖。我會有很少的約束，比如已經有了一些定向關係。

Answer 1

您實際上正在嘗試從您的基礎架構圖構建一個DAG。請注意，有向圖是一個DAG，當且僅當它可以是topologically sorted。

所以，讓我們從頭到尾走。首先創建拓撲排序，然後以符合排序的方式連接節點。

• 首先，刪除所有「未確定」的邊緣，只保留那些已經有指示的邊緣。
• 然後，對圖進行拓撲排序並找到一些拓撲排序（如果沒有，則無法使用給定的限制來解決問題）。
• 基於此，從第一個到最後一個設置每個邊的方向，使得源節點是具有較低拓撲排序的那個。

算法的時間複雜度在節點和邊的數量上是線性的。