圖中的邊緣交叉減少

Question

我想問你是否有任何算法如何最小化圖中的邊緣交叉，例如如果我有圖的轉換矩陣。

我發現像嘗試將節點放在其他節點周圍的方法，但我想知道一些其他的想法。謝謝。

Answer 1

有一系列已經建立的圖形繪製應用程序已經建立的算法/庫，你可以得到一些背景here。

爲了繪製無向圖，流行的選擇是基於力的佈局算法，其中圖形邊緣被視爲彈簧（吸引力），而頂點被視爲帶電粒子（應用排斥力）。該算法通過基於這些力更新頂點位置來工作，直到達到穩定狀態。你可以閱讀更多關於基於力的方法here。由於這些算法搜索均衡解決方案，它們通常會導致僞優化佈局，沒有太多邊緣纏結。

您可能有興趣使用可用的許多圖形繪製庫之一。 Graphviz軟件包通常非常好，並支持多種不同的算法用於不同的圖形繪製應用程序。