2

Boruvka アルゴリズム (http://en.wikipedia.org/wiki/Bor%C5%AFvka's_algorithm) は無向グラフでのみ機能しますか?

たとえば、次のようなグラフ構造があるとします。

node 1 -> node 2 (weight 1), node 3 (weight 1), node 4 (weight 1)

node 2 -> node 3 (weight 2)

node 3 -> node 4 (weight 2)

node 4 -> node 2 (weight 2)

次に、最小スパニング ツリーにエッジを含める必要があります。

1 -> 2

1 -> 3

1 -> 4

しかし、Boruvkaのアルゴリズムは吐き出します

1 -> 2

2 -> 3

3 -> 4

Boruvka はまず個々のノードを調べ、そのノードから出ている最短のエッジを MST に追加するためです。

ウィキペディアの記事で、エッジの重みは異なる必要があると書かれていることは知っていますが、ノード 1 から出てくるすべてのエッジの重みが (ノード 2 ～ 4 からの) 「外側の」エッジの重みよりも小さい限り、Boruvka のように見えます。アルゴリズムは失敗します。無向ではなく有向グラフだからでしょうか。

4

3 に答える 3

2

無向ではなく有向グラフだからでしょうか。

はい。有向グラフの場合、入力エッジと出力エッジを考慮する必要があり、アルゴリズムは同じように機能します。これを行う最も簡単な方法は、基になる無向グラフを検討することです。

于 2012-12-11T03:35:01.833 に答える
1

最小スパニング ツリーは無向グラフでのみ定義されるため、これを考慮に入れて質問しても意味がありません。おそらく、同じ頂点セットとエッジの重みの最小合計を持つ元のグラフの強く接続された誘導サブグラフなど、何か他のものを探しています。この場合、ツリーを取得する必要はありません。実際、ツリーは無向グラフとしても定義されています。これを解決するIMHOアルゴリズムは、計算上難しい問題になります。

于 2012-12-11T16:11:04.227 に答える
1

自問すべき質問は、有向グラフの「最小スパニング ツリー」とは何を意味するのかということです。使用するアルゴリズムは、この質問に対する答えによって異なります。

于 2012-12-11T08:25:25.967 に答える