ツリーを生成しますか?

最小身長木-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)

動作原理

任意幹線

を選択

選択した幹線の頂点から最も重みの低い頂点

を選択する.
すべての頂点が選択されるまで、

を繰り返します.