重み付けされたグラフから2番目に小さい最小スパニングツリーを見つけるアルゴリズム

Question

重み付けされた無向グラフから2番目に小さい最小スパニングツリー3を見つけようとしています。私は、クラスカルのアルゴリズムを使用してMSTを計算する方法を知っている、と私は2番目の最高の最小化アルゴリズムにこの方法を見つけるために考えていた：

ステップ：

1. ソートすべてのグラフのエッジを。

2. 計算

3. 最初MSTにないグラフから最小の重みエッジを取得し、MST（今MSTを有するサイクル）

4. 除去するためにそれを追加クラスカル

   を使用してMST新しく形成されたサイクルの最大ウェイトエッジ

これは2番目に良いMSTの権利ですか？

私が知っているところでは、各MSTエッジの間を繰り返し、エッジが選択されていないグラフ上でKruskalを実行するアルゴリズムを指摘しているトピックがあります。

Answer 1

動作しません。

ステップ3の後、新たに追加されたエッジは、コストが非常に低いエッジのみを含むサイクルの一部になる可能性があるため、ステップ3および4の後に、MSTの全体コストが大幅に増加する可能性があります。

一方、グラフには、手順3で選択したものと同様のコストを持つ別のエッジが含まれている場合があります。これは、MSTに追加すると、コストが比較的高いエッジを含むサイクルの一部になります。ステップ3でこのエッジを選択してからステップ4を適用すると、提案されたアルゴリズムで生成されたものよりも優れた別のスパニングツリーが作成されます。

Answer 2

いいえ、アルゴリズムが機能しません。

1  3 
/--\ 2 /--\ 
. .---. . 
\--/  \--/ 
    4  5 

MSTがある1,2,3 => 6.

次善である1,2,5 => 8.

あなたのアルゴリズムは2,3,4を返します= >

9.（私はあなたのステップ4で追加したばかりの1ではありません最大重量エッジを返すことであると仮定しています）

---

鍵はここにあります1と4の差（3）が3と5の差（2）よりも大きいため、3を5に置き換えると、1を4で置き換えるよりも全体コストが低くなります。