3

接続されたグラフのエッジの数が既知であり、各エッジの重みが異なると仮定すると、線形時間で最小スパニング ツリーを作成することは可能でしょうか?

これを行うには、各エッジを確認する必要があります。このループ中に検索を含めることはできません。それ以外の場合は、少なくとも n log n 時間になります。ループ内を検索せずにこれを行う方法がわかりません。つまり、どういうわけか、各エッジを 1 回だけ見て、それを含めるかどうかを、成長するデータ構造を含まない「静的な」以前の値に基づいて決定する必要があります。

問題のノードのエンドポイントを保持し、次のノードを見て、次のノードが前のノードと同じ頂点を持っている場合は、前のノードと現在のノードの重みを比較して、低いノードを保持するとします。現在のノードのエンドポイントが前と等しくない場合、それは別のコンポーネントにあります..各エッジを線形で調べながら、すでに追加されているコンポーネントノードを追跡するためのハッシュまたは配列を作成できないため、スタックしています。時間。

私が考えた別のアプローチは、最小の重みでエッジを見つけることです。エッジの重みが異なるため、このエッジは MST の一部になります。それから..私は立ち往生しています。線形時間で n - 1 個のエッジに対してこれを行うことはできないためです。

ヒントはありますか？

編集

ノードの数、エッジの数、および各エッジの重みが異なることがわかっている場合はどうなるでしょうか? たとえば、n 個のノード、n + 6 個のエッジがあるとします。

次に、正しい 7 つのエッジを見つけて削除するだけでよいでしょうか?

4

4 に答える 4

2

私の知る限りでは、グラフにいくつのエッジがあり、それらが異なることを知ることによって、MST をより速く計算する方法はありません。最悪の場合、最小コストのエッジ (MST にある必要があります) を見つける前に、グラフ内のすべてのエッジを調べる必要があり、最悪の場合、Ω(m) 時間かかります。したがって、 MST アルゴリズムは最悪の場合でも Ω(m) 時間かかると主張します。

ただし、最悪のケースで既に Ω(m) 作業を行っている場合は、任意の MST アルゴリズムで次の前処理ステップを実行できます。

  1. 端をスキャンして、いくつあるか数えます。
  2. 各エッジの重みにイプシロン値を追加して、エッジが一意であることを確認します。

これは、時間 Ω(m) でも行うことができます。したがって、エッジの数とエッジのコストが異なることを認識して MST の計算を高速化する方法があれば、現在の MST アルゴリズムでこの前処理ステップを実行して、パフォーマンスを高速化しようとします。私の知る限り、パフォーマンス上の理由からこれを実際に実行しようとする MST アルゴリズムはないため、この余分な知識に基づいてより高速な MST アルゴリズムを取得する (既知の) 方法はないと思います。

お役に立てれば！

于 2013-05-31T23:54:33.543 に答える