algorithm - すべてのポイント間の最短接続を見つける方法は?

Question

最初の図のように、点がマークされた 2 次元配列があります。私がしなければならないことは、そのマップ上のすべてのポイント間の接続を見つけることです (したがって、任意のポイントから他のすべてのポイントに移動できます)。すべてのエッジの長さの合計は、可能な限り最小でなければなりません。

入力：

(0, 0) (5, 5) (5, 1) (4, 4) (1, 5) (2, 4) (2, 1) // 1st,2nd,3rd city ...

出力：

1-7, 7-3, 7-6, 6-5, 6-4, 4-2

Answer 1

入力したポイントのセットを完全に接続されたグラフとして扱い、ポイントのペア間の距離をエッジの重みとして扱います。次に、グラフの最小全域木を見つけます。

クラスカルのアルゴリズムは特に簡単です。

• 出力グラフにエッジがない状態から始めます。
• 入力グラフの各エッジを、重みの順に、小さいものから順に調べます。
  • 2つの頂点が出力グラフの同じツリーの一部になっていない場合は、出力グラフにエッジを追加します。

速度が問題になる場合は、これを非常に高速にするために使用できるさまざまな手法があります。