疎なグラフと密なグラフに関して、Prim と Kruskal の時間の複雑さが異なる理由を理解しようとしています。それぞれがどのように機能するかを示すいくつかのアプレットを使用した後でも、グラフの密度がアルゴリズムにどのように影響するかについて、まだ少し混乱しています。誰かが私に正しい方向への微調整をしてくれることを願っています。
4858 次
3 に答える
4
ウィキペディアでは、これらのアルゴリズムの複雑さを、エッジの数であるEと頂点の数であるVで示しています。これは、この種の分析を正確に実行できるため、優れた方法です。
クラスカルのアルゴリズムは O( E log V ) です。Prim の複雑さは、使用するデータ構造によって異なります。隣接行列を使用すると、O( V 2 ) になります。
ここで、 EにV 2をプラグインすると、コメントで引用した密なグラフの複雑さが得られます。 EにVをプラグインすると、スパースなグラフが得られます。
密なグラフにV 2をプラグインするのはなぜですか? 最も密度の高いグラフでも、 V 2ほど多くのエッジを持つことはできないため、明らかにE = O( V 2 ) です。
スパース グラフにVをプラグインするのはなぜですか? スパースの意味を定義する必要がありますが、各頂点のエッジが 5 つ以下の場合、グラフをスパースと呼ぶとします。そのようなグラフは非常にまばらであると言えます。数千の頂点に達すると、隣接行列はほとんど空のスペースになります。これは、スパース グラフの場合、E ≤ 5 Vであるため、E = O( V ) であることを意味します。
于 2010-01-06T16:01:10.853 に答える
1
ひょっとして頂点の数に関してこれらの異なる複雑さはあるのでしょうか?
まばらなグラフの場合、エッジの数 E = O(V) で、V は頂点の数、密なグラフの場合は E = O(V^2). 両方のアルゴリズムが潜在的に E に依存する複雑さを持っているため、これを V に依存する複雑さに変換すると、密グラフまたは疎グラフに応じて異なる複雑さが得られます。
編集：
もちろん、ウィキペディアにはこれについての内訳がありますが、さまざまなデータ構造も複雑さに影響します
于 2010-01-06T09:39:15.973 に答える
0
Cormen らによる Algorithms は、どちらの場合もグラフのスパース表現を使用して実際に分析を行います。Kruskal のアルゴリズム (バラバラなコンポーネントの頂点をすべてが結合するまでリンクする) では、最初のステップはグラフのエッジをソートすることです。これには O(E lg E) の時間がかかり、これより長くかかるものは他にないことを単純に確立します。プリムのアルゴリズム (現在のツリーにまだ存在しない最も近い頂点を追加することによって現在のツリーを拡張する) では、フィボナッチ ヒープを使用して保留中の頂点のキューを格納し、O(E + V lgV) を取得します。フィボナッチ ツリーでは頂点までの距離が減少するためです。キュー内は O(1) のみであり、これはエッジごとに最大 1 回実行します。
于 2010-01-06T19:53:20.053 に答える