隣接リストで表されるグラフと、親配列で表される彼の MST があります。
私の問題は、グラフからエッジを削除し、親配列を更新する必要があることです。
私はすでに次の場合に対処しています。
エッジが MST にあり、グラフのエッジがサイクルにある場合、どうすればよいですか? これをO(n+m) complexで行う必要があります。
エッジのコストを赤色で書きます。
現在切断されているツリー部分からツリーの残りの部分への最小距離パスを検索し、そのパスを間に追加します。これが単一のエッジです。
元のツリーを T とします。エッジを削除すると、ツリー T1 と T2 に分割されます。
これらのうちの 1 つを取り、T2 とします。T2 上のノードに付随するすべてのエッジは、T2 上にあるか、T2 を T1 に接続するエッジです。T2 上のノードに付随するこれらのエッジの中で、((もう一方の端が T1 ノードにある) および (そのようなすべてのエッジの中で最小のコストを持つ)) のものを選択します。このエッジの検索、たとえば e=(u,v) には O(|E|) の時間がかかります。分離された部分がリーフの場合は O(|N|)。
T1 \union T2 \union {e} よりもコストが低いツリー (T' など) があった場合、T1 と T2 のノード セット N1 と N2 は、1 つのエッジだけでなく、より多くの相互接続を持つことになります。
すなわち、T' には、N1 のノードで始まり N2 のノードで終わる 2 つ以上のエッジがあります。それ以外の場合、((T1 と T2 は N1 と N2 に対する最小スパニング ツリーです) および (e は T1 と T2 間の最小コストの接続です)) は false になります。しかし、T1 と T2 の間の移動は、e=(u,v)-- 矛盾よりもコストがかかります。
いくつかの証明の詳細をスキップしました。お役に立てれば。