algorithm - 新しいノードを追加した後にMSTを見つける方法は？

Question

MST (Minimum Spanning Tree)新しいノードを追加した後、またはウェイの距離を変更した後、どのように見つけますか？

これを解決するために助けが必要です。誰か助けてもらえますか？

ありがとう。

Answer 1

新しいエッジを追加する場合：

グラフトラバーサルを実行する必要があります。最も簡単なのは、変更された/新しいエッジのいずれかの側から、このためのDFSです。以前に行っていたノードに戻ることができる場合は、サイクルがあります。

そのサイクルでは、最大のエッジを削除する必要があります。あなたは再び木を手に入れるでしょう、そしてそれは最小のスパンのものです。

エッジの重みを変更する場合は、次のことを行う必要があります。

• 新しいエッジを一時的に削除して、グラフをAとBの2つのコンポーネントに切断します。
• 新しいエッジの重みが以前よりも小さい場合は、元に戻すことができます。それ以外の場合：
• 以前に処理したエッジを繰り返し処理し、それらがAからBに結合しているかどうかを確認します。
• それらから最小のエッジを選択し、そのエッジを使用してコンポーネントを接続します。

ここでも、新しい最小スパニングツリーが得られます。

全体として、これはO(V+E)逆アッカーマンの小さな係数の1倍です。