最小スパニングツリーと最短パスツリー
1. 序章
このチュートリアルでは、最小スパニングツリーと最短パスツリーの2つの問題に焦点を当てます。 同様の構造を持つ欲張りアルゴリズムを使用して、両方の問題を解決できます。
2. スパニングツリー
無向グラフGのスパニングツリーは、可能な限り最小のエッジ数ですべてのグラフノードをカバーする接続されたサブグラフです。一般に、グラフには複数のスパニングツリーがあります。
次の図は、スパニングツリーを使用したグラフを示しています。 スパニングツリーのエッジは赤で表示されます。
3. 最小スパニングツリー
グラフがエッジで重み付けされている場合、スパニングツリーの重みをそのすべてのエッジの重みの合計として定義できます。
次の図は、エッジ加重グラフの最小スパニングツリーを示しています。
この問題は、Prim、Kruskal、 Boruvkaなどのいくつかのアルゴリズムで解決できます。 プリムのアルゴリズムは、最短経路ツリーの問題の解決策と同様の構造を持っているため、紹介しましょう。
視覚的に、サンプルグラフの最小スパニングツリーに対してプリムのアルゴリズムを段階的に実行してみましょう。
プリムのアルゴリズムの時間計算量は、グラフに使用されるデータ構造によって異なります。
たとえば、隣接リストを使用してグラフを表し、エッジを優先キューに格納する場合、全体的な時間計算量は O（E log V）です。ここで、 V はグラフ内のノードの数であり、Eはエッジの数です。 また、グラフを表すために隣接行列を使用する場合、全体的な時間計算量は O（V2）です。
4. 最短経路ツリー
最短経路ツリーの問題では、ソースノードsから始めます。
グラフGのその他のノードv の場合、sとvの間の最短経路は、このパスに沿ったエッジは最小化されます。 したがって、最短経路ツリー問題の目的は、ソースノードsから他のノードvへのパスがGで最短パスになるようなスパニングツリーを見つけることです。
この問題は、ダイクストラのアルゴリズムで解決できます。
ダイクストラのアルゴリズムは、プリムのアルゴリズムと同様の構造を持っています。 ただし、選択基準は異なります。
サンプルグラフでソースノード番号0のダイクストラのアルゴリズムを段階的に視覚的に実行してみましょう。
ノード0とノード3の間の最短パスは、パス0->1->3に沿っています。 ただし、ノード1とノード3の間のエッジは、最小スパニングツリーにありません。 したがって、生成される最短パスツリーは最小スパニングツリーとは異なります。
プリムのアルゴリズムと同様に、時間計算量もグラフに使用されるデータ構造に依存します。 隣接行列を使用してグラフを表す場合、全体的な時間計算量は O（V2）です。 また、隣接リストを使用してグラフを表し、エッジを優先キューに格納すると、全体的な時間計算量は O（E log V）。になります。
5. 結論
このチュートリアルでは、最小スパニングツリーと最短パスツリーという2つの同様の問題について説明しました。 また、プリム法とダイクストラ法のアルゴリズムの違いを比較しました。
