分散型最小全域木

コアに隣接する2つのノードは、フラグメント内の他のノードにメッセージをブロードキャストします。メッセージはブランチエッジを経由して送信されますが、コアは経由しません。各ブロードキャストメッセージには、フラグメントのIDとレベルが含まれています。この段階の終了時には、各ノードは新しいフラグメントIDとレベルを受信して​​います。

この段階では、フラグメント内のすべてのノードが協力して、フラグメントの最小重みの発信エッジを見つけます。発信エッジとは、他のフラグメントに接続するエッジのことです。この段階で送信されるメッセージは、ブロードキャスト段階とは逆方向です。すべてのリーフノード（分岐エッジを1つだけ持つノード）によって初期化されたメッセージが、分岐エッジを介して送信されます。メッセージには、検出された接続先の発信エッジの最小重み（そのようなエッジが見つからなかった場合は無限大）が含まれます。最小発信エッジを見つける方法は後ほど説明します。各非リーフノードについて、その分岐エッジの数を次のようにします。${\displaystyle n}$受け取った後${\displaystyle n-1}$コンバージキャストメッセージの場合、メッセージから最小の重みを選択し、そのメッセージから発信されるエッジの重みと比較します。最小の重みが、ブロードキャストを受信したブランチに送信されます。

前の段階が完了すると、コアで接続された2つのノードは、受信した最適なエッジを互いに通知できます。次に、フラグメント全体から最小の発信エッジを特定します。コアから最小の発信エッジへ、分岐エッジのパスを介してメッセージが送信されます。最後に、選択された発信エッジを介してメッセージが送信され、そのエッジが接続する2つのフラグメントを結合するように要求します。2つのフラグメントのレベルに応じて、2つの結合操作のうちの1つが実行され、新しいフラグメントが形成されます。詳細は後述します。

前述のように、各ノードはコアからブロードキャストメッセージを受信した後、最小重みの発信インシデントエッジを見つける必要があります。ノードが${\displaystyle n}$ブロードキャストを受信すると、最小重みの基本エッジを選択し、ノードにメッセージを送信します。${\displaystyle n'}$反対側にはフラグメントのIDとレベルがあります。次に、ノード${\displaystyle n'}$エッジが送信エッジであるかどうかを判断し、通知ノードにメッセージを送信します。${\displaystyle n}$結果について。決定は以下のとおり行われます。

1. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)={\mathit {Fragment}}_{\mathit {ID}}(n')}$つまり、ノード${\displaystyle n}$そして${\displaystyle n'}$同じフラグメントに属しているため、エッジは外部に向いていません。
2. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')}$そして$\displaystyle {\mathit {Level}}(n)\leq {\mathit {Level}}(n')}$つまり、ノード${\displaystyle n}$そして${\displaystyle n'}$異なる断片に属するため、エッジは外向きです。
3. ${\displaystyle {\mathit {Fragment}}_{\mathit {ID}}(n)\neq {\mathit {Fragment}}_{\mathit {ID}}(n')}$そして$\displaystyle {\mathit {Level}}(n)>{\mathit {Level}}(n')}$結論を出すことはできません。理由は、2 つのノードが既に同じフラグメントに属している可能性があるからです。${\displaystyle n'}$ブロードキャストメッセージの遅延のため、この事実はまだ発見されていません。この場合、アルゴリズムはノードを${\displaystyle n'}$応答のレベルがノードから受信したレベル以上になるまで応答を延期する${\displaystyle n}$。

させて${\displaystyle F}$そして${\displaystyle F'}$これら 2 つの断片を結合する必要があります。これを行うには 2 つの方法があります。^{[ 1 ] [ 6 ]}

• マージ: この操作は、両方が${\displaystyle F}$そして${\displaystyle F'}$共通の最小重量の発信エッジを共有し、${\displaystyle {\mathit {Level}}(F)={\mathit {Level}}(F')}$結合された断片のレベルは${\displaystyle {\mathit {Level}}(F)+1}$。
• 吸収: この操作は、$\displaystyle {\mathit {Level}}(F)<{\mathit {Level}}(F')}$結合されたフラグメントは、${\displaystyle F'}$。

さらに、「吸収」操作が発生すると、${\displaystyle F}$コアを変える段階にある必要があるが、${\displaystyle F'}$は任意の段階にある可能性があります。したがって、「吸収」操作は、状態に応じて異なる方法で行われる可能性があります。${\displaystyle F'}$。 させて${\displaystyle e}$エッジになる${\displaystyle F}$そして${\displaystyle F'}$組み合わせたい、そして${\displaystyle n}$そして${\displaystyle n'}$2 つのノードは接続されています${\displaystyle e}$で${\displaystyle F}$そして${\displaystyle F'}$それぞれ、次の2つのケースを考慮する必要があります。

前述のとおり、フラグメントは「マージ」または「吸収」操作によって結合されます。「吸収」操作では、すべてのフラグメントの最大レベルは変更されません。「マージ」操作では、最大レベルが 1 増加する場合があります。最悪の場合、すべてのフラグメントが「マージ」操作で結合されるため、各レベルのフラグメントの数は半分になります。したがって、最大レベル数は${\displaystyle O(\log V)}$、 どこ${\displaystyle V}$はノードの数です。