Kruskalsアルゴリズムを説明しました

Question

私は現在、いくつかのアルゴリズムで少し遊んでいて、Kruskalsアルゴリズムを見つけました。

概念を理解し、実際のプロセスを行う方法を理解してください。しかし、アルゴリズムを理解していない。ここで

はアルゴリズムです：| Vを、私は、把握することができたものから

|すべての頂点ですか？

E 'とは何ですか？ なぜこのアルゴリズムが私をそんなに混乱させているのか分かりません。私は絶対の容易さで他のものを取りました。

Answer 1

Kruskalのアルゴリズムは、サイクルを導入しない限り、ウェイトの順にMSTにエッジを追加します典型的には共用体を使用して行われる。を見つける）。コードは、いくつかの値を初期化することによって開始：

n := |V| // the number of vertices 
E' := ∅ // the edges in our MST; it starts as the empty set 
Cands = E // the edges still under consideration for adding to the MST, starts as all edges 

ループ条件は次のとおりです。

私たちは、これは数ある知っているので、私たちがいる限り、我々は n - 1エッジ（より少ないを選択したとして継続されて

while |E'| < n - 1 and Cands != ∅ do 

任意のスパニングツリーに含まれるエッジの数：それらが見つかった場合は終了します）、まだ考慮していないエッジのセットは空ではありません。

行（1）と（2）は、最小重みの端がCandsにあり、セットから削除します。 Candsの適切な構造は、min-heapです。この場合、これは単なるポップ操作です。

行（3）と（4）は、（1）のCandsから検索したエッジが、追加された場合はE'にサイクルを導入するかどうかを決定します。そうでなければ、このエッジがMSTにあることがわかります。それ以外の場合はそうではありません。

最後の行は、実際にツリーが見つかったかどうかを確認するだけです。たとえば、グラフが1つの接続されたコンポーネントでない場合など、ループが終了して、n - 1のエッジが見つからない可能性があります。