Looking for algorithm Answers? Try Ask4KnowledgeBase
Looking for algorithm Keywords? Try Ask4Keywords
algorithmKruskalのアルゴリズム
備考
Kruskalのアルゴリズムは、グラフの最小スパニングツリー（MST）を見つけるために使用される欲張りアルゴリズムです。最小スパニングツリーは、グラフのすべての頂点を接続し、最小の合計エッジ重みを持つツリーです。
Kruskalのアルゴリズムは、 最小ウェイト （MSTにはまだない）を繰り返し選択し、そのエッジで接続された2つの頂点がMSTにまだ接続されていない場合は最終結果に追加します。 Union - データ構造を使用して、2つの頂点がすでにMSTに接続されているかどうかを確認できます。 MSTのいくつかのプロパティは次のとおりです。
-
n個の頂点を有するグラフのMSTは、厳密にn-1n辺を有する。 - 各頂点から他のすべての頂点までの固有のパスが存在します。
Kruskalのアルゴリズム 関連する例
This modified text is an extract of the original Stack Overflow Documentation created by following contributors and released under CC BY-SA 3.0
This website is not affiliated with Stack Overflow
Email: tutorialpedia@outlook.com