8

Robert Sedgewick のアルゴリズムに関する本からこの質問があります。

クリティカル エッジ。グラフから削除すると MST の重みが増加する MST エッジは、クリティカル エッジと呼ばれます。E log E に比例する時間で、グラフ内のすべての重要なエッジを見つける方法を示してください。注: この質問は、エッジの重みが必ずしも明確ではないことを前提としています (そうでない場合、MST 内のすべてのエッジが重要です)。

この問題を解決するアルゴリズムを提案してください。

私が考えることができる 1 つのアプローチは、時間通りに仕事をします EV 私のアプローチは、クルスカルのアルゴリズムを実行することです。

ただし、MST への挿入によってサイクルが作成されるエッジに遭遇したときはいつでも、そのサイクルに同じエッジの重みを持つエッジが既に含まれている場合、既に挿入されているエッジはクリティカル エッジではありません (そうでない場合、他のすべての MST エッジはクリティカル エッジです)。 .

このアルゴリズムは正しいですか？このアルゴリズムを拡張して、時間 E log E でジョブを実行するにはどうすればよいですか?

4

2 に答える 2

7

エッジがクリティカルな場合に提案する条件は正しいと思います。しかし、実際にサイクルを見つけて、その各エッジをテストする必要はありません。

Kruskal アルゴリズムは、重みの昇順でエッジを追加するため、一連のエッジ追加を同じ重みのエッジ追加のブロックに分割できます。各等重量ブロック内で、同じ 2 つのコンポーネントを結合するエッジが複数ある場合、これらのエッジはすべて重要ではありません。これは、他のエッジのいずれかが代わりに選択される可能性があるためです。(入力の一部として特定の MST が実際に与えられていないため、それらはすべて非クリティカルであると言います。もしそうであれば、これは非クリティカルと呼ぶ特定のエッジを識別します。Kruskal が実際に選択するエッジは、単なる初期エッジ順序付けのアーティファクトまたはソートの実装方法)。

しかし、これだけでは十分ではありません。重み 4 以下のすべてのエッジを MST に追加した後、構成要素のペア (1, 2)、(2, 3) および（1、3）。コンポーネント ペアは、これら 3 つのエッジのうち 1 つ以上によって結合されていませんが、必要なのは (任意の) 2 つだけです。3 つすべてを使用すると、サイクルが作成されます。

重みが w である等重みブロックごとに、実際に行う必要があるのは、(概念的に) これまでの MST の各コンポーネント (つまり、重み < w を持つエッジを使用) が頂点である新しいグラフを作成することです。これらのコンポーネント間に重み w エッジがある場合は常に、2 つの頂点間のエッジです。次に、このグラフの各コンポーネントで DFS を実行してサイクルを検出し、そのようなサイクルに属するすべてのエッジを非クリティカルとしてマークします。DFS には O(nEdges) 時間がかかるため、各ブロック (サイズの合計が E) の DFS 時間の合計は O(E) になります。

Kruskal のアルゴリズムは、O(Elog E) ではなく、O(Elog E) の時間がかかることに注意してください。Bernard Chazelle のような人々は線形時間の MST 構築に近づいていますが、TTBOMK はまだそこに到達していません! :)

于 2013-03-30T18:57:59.260 に答える
5

はい、あなたのアルゴリズムは正しいです。クラスカルのアルゴリズムの実行を、いくつかの MST エッジ e のコストが無限大に変更される同様の実行と比較することで、それを証明できます。最初の実行で e が考慮されるまで、両方の実行は同一です。e の後、最初の実行では、2 番目の実行よりも連結要素が 1 つ少なくなります。この条件は、エッジ e' が 2 回目の実行で e が持つコンポーネントを結合すると見なされるまで持続します。これまでに構築されたフォレストの違いはエッジ e だけなので、e' によって作成されたサイクルに属している必要があります。e' の後、実行は同じ決定を行います。フォレストの違いは、最初の実行には e があり、2 番目の実行には e' があることです。

このアルゴリズムを実装する 1 つの方法は、動的ツリー (ラベル付きフォレストを表すデータ構造) を使用することです。この ADT の 1 つの構成は、対数時間で次のメソッドをサポートします。

  • MakeVertex() - 新しい頂点を構築して返します。
  • Link(u, c, v) - 頂点 u と v が接続されていてはなりません。頂点 u から頂点 v へのマークされていないエッジをコスト c で作成します。
  • Mark(u, v) - 頂点 u と v はエッジ e の終点でなければなりません。マークス e.
  • Connected(u, v) - 頂点 u と v が接続されているかどうかを示します。
  • FindMax(u, v) - 頂点 u と v が接続されている必要があります。u から v までの一意のパス上にあるマークされていないエッジの終点を、最大コストとそのコストで返します。このエッジの端点は、パスに表示される順序で指定されます。

これが実際に優れたアルゴリズムであるとは主張しません。スイス アーミー ナイフのようなダイナミック ツリーは用途が広いですが、複雑であり、多くの場合、最適なツールとは言えません。すべてのエッジが処理されるまで待ってクリティカル エッジが何であるかを判断できるという事実を利用する方法を検討することをお勧めします。

于 2013-03-30T18:24:21.737 に答える