-1

はい、これは宿題です。最小全域木を決定するためのSollin（またはBorůvka）アルゴリズムのプロセスを誰かが説明できるかどうか疑問に思いました。また、最悪の場合の反復回数を決定する方法を説明できれば、それは素晴らしいことです。

4

2 に答える 2

6

トップレベルでは、アルゴリズムは次のように機能します。

  • 一部のサブグラフには、多数のスパニングツリーがあることを確認してください。最初は、グラフのすべての頂点はエッジのないmstです。
  • 各反復で、スパニングツリーごとに、別のスパニングツリーに接続する最も安価なエッジを見つけます。（これは単純化です。）

反復に関する最悪のケースは、常にツリーのペアをマージすることです。その場合、ツリーの数は各反復で半分になるため、反復の数はノードの数の対数になります。

また、追加するエッジの選択には特別なトリックが含まれることに注意してください。注意しないと、ツリーAがツリーBに接続し、ツリーBがツリーCに接続し、ツリーCがツリーAに接続するときに円が導入される可能性があります。（これは、選択した3つのエッジすべての重みが同じである場合にのみ発生します。秘訣は、エッジの順序が固定されているように、任意であるが固定されたタイブレーカーを使用することです。）

これが私のバックオブインデックスカードの概要です。

于 2010-11-19T20:57:20.140 に答える
0

私は素人の用語を使用しています。

  • 最初に頂点を選択します
  • その頂点からすべてのエッジをチェックし、重みが最小のエッジを選択します
  • すべての頂点に対してこれを行います（一部のエッジは複数回選択される場合があります）
  • 接続されたコンポーネントを取得します。
  • これらの接続されたコンポーネントから、最小の重みを持つ1つのエッジを選択します。

最小重量のスパニングツリーが形成されます

于 2013-01-23T14:30:29.507 に答える