[アルゴリズム]最小拡張ツリー(MST)

1513 ワード
クリーム prim クルースカ greedy MST アルゴリズム#アルゴリズム# kruskal さいしょうのびじゅ テキストリンク

ツリーを生成しますか?


最小身長木-MST?


MSTアルゴリズム

1. Kruskal 알고리즘
2. Prim 알고리즘
 

ツリーを生成しますか?


グラフィック内のすべての頂点を含むツリー
=図の最小接続部分ツリー!
=図形から幹線部分を選択して作成するツリー
=>従って幹線数が最小:n-1
1つの図には多くの伸長木が存在することができる.
守らなければならないのは、すべての頂点が接続され、サイクを含まないことです.
DFS、BFSは新しいツリーの検索をサポート
腎臓樹
腎臓樹X
 

最小身長木-MST?


Minimum Spanning Tree
幹線の重量を考慮して、最小コストの伸び木を選びます!
  • 幹線の重み付けと最小
  • 本線はn-1(伸び木だから~)
    • でなければなりません
  • サイクル(腎臓樹だから~22)
    • がないといけない
     

    MSTアルゴリズム


    2種類:Kruskalアルゴリズム/PRimアルゴリズム

    1.Kruskalアルゴリズム

  • MST最小コストの幹線/ループXに基づいて、各ステップでループを構成しない最小コスト幹線を選択:無条件に最小幹線
    • を選択し、前のステップで作成した新しいツリーを考慮しない
  • 貪欲な方法:すべての頂点を最低コストで接続するための最良の答えを求める
  • 幹線本数が少ない場合、ガラス
  • 幹線を主とする:幹線でソートするには長い時間(ソート)がかかる
  • 時間複雑度:O(EGE)=O(EGV^2)=O(2*EGV)=O(EGV)

    • 動作原理

  • すべての幹線の重み付けは昇順に
    • 並べられている.
  • 重み最小の幹線
    • を選択する.
  • で選択した幹線で接続する2つのノードが接続されていない場合は、2つのノードが接続されます.
    • この手順を繰り返します

    •  

    2.Primアルゴリズム

  • の開始点から、伸長ツリーのセットを徐々に拡張します.前のステップで作成した伸長ツリー
    • を拡張します.
  • 幹線本数が多い時ガラス
  • 頂点を主とする
  • 時間複雑度:O(対数E)=O(対数V)

    • 動作原理

  • 任意幹線
    • を選択
  • 選択した幹線の頂点から最も重みの低い頂点
    • を選択する.
    すべての頂点が選択されるまで、
  • を繰り返します.
    • ACE学習簡易記録
    🔎 HTML (5-2)