Data-structures-algorithms-kruskals-spanning-tree-algorithm
クラスカルのスパニングツリーアルゴリズム
最小コストのスパニングツリーを見つけるためのクラスカルのアルゴリズムは、貪欲なアプローチを使用します。 このアルゴリズムは、グラフをフォレストとして扱い、グラフが持つすべてのノードを個別のツリーとして扱います。 ツリーは、使用可能なすべてのオプションの中で最もコストが低く、MSTプロパティに違反しない場合にのみ、別のツリーに接続します。
クラスカルのアルゴリズムを理解するために、次の例を考えてみましょう-
手順1-すべてのループと並列エッジを削除する
指定されたグラフからすべてのループと平行エッジを削除します。
平行なエッジの場合、関連するコストが最も少ないエッジを保持し、他のすべてを削除します。
ステップ2-重みの昇順ですべてのエッジを配置します
次のステップでは、エッジとウェイトのセットを作成し、それらをウェイト（コスト）の昇順で配置します。
ステップ3-重みが最小のエッジを追加します
次に、重みが最小のグラフからエッジを追加し始めます。 全体を通して、スパニングプロパティが損なわれていないことを確認し続けます。 1つのエッジを追加することにより、スパニングツリープロパティが保持されない場合、グラフにエッジを含めないことを検討します。
最小コストは2で、関係するエッジはB、DおよびD、Tです。 それらを追加します。 それらを追加してもスパニングツリーのプロパティに違反しないため、次のエッジ選択に進みます。
次のコストは3で、関連するエッジはA、CおよびC、Dです。 私たちはそれらを再び追加します-
表の次のコストは4です。これを追加すると、グラフに回路が作成されることがわかります。 −
無視します。 このプロセスでは、回路を作成するすべてのエッジを無視/回避します。
コスト5および6のエッジも回路を作成することがわかります。 それらを無視して先に進みます。
追加するノードは1つだけです。 7と8の2つの最小コストエッジの間に、コスト7のエッジを追加します。
エッジS、Aを追加することにより、グラフのすべてのノードが含まれ、最小コストのスパニングツリーが作成されました。
