3

隣接リストで表されるグラフと、親配列で表される彼の MST があります。

私の問題は、グラフからエッジを削除し、親配列を更新する必要があることです。

私はすでに次の場合に対処しています。

  1. エッジは存在しません。
  2. エッジはグラフにありますが、MST にはありません (MST は変化しません)。
  3. エッジは 2 つのノードからの唯一のパスです (この場合、グラフが接続されていないため、null を返します)。

エッジが MST にあり、グラフのエッジがサイクルにある場合、どうすればよいですか? これをO(n+m) complexで行う必要があります。

エッジのコストを赤色で書きます。

4

1 に答える 1

3

現在切断されているツリー部分からツリーの残りの部分への最小距離パスを検索し、そのパスを間に追加します。これが単一のエッジです。

元のツリーを 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)-- 矛盾よりもコストがかかります。

いくつかの証明の詳細をスキップしました。お役に立てれば。

于 2012-12-02T01:16:11.610 に答える