0

重みのある無向連結グラフが与えられます。w:E->{1,2,3,4,5,6,7} - 可能な重みは 7 つしかないことを意味します。O(n+m) の Prim のアルゴリズムと O( m*a(m,n)) の Kruskal のアルゴリズムを使用してスパニング ツリーを見つける必要があります。

これを行う方法がわかりません。ここでウェイトがどのように役立つかについてのガイダンスが本当に必要です.

4

2 に答える 2

3

エッジの重みをより速く並べ替えることができます。

Kruskal アルゴリズムでは、O(M lg M) ソートは必要ありません。カウント ソート (または他の O(M) アルゴリズム) を使用できます。したがって、最終的な複雑さは、ソートの場合は O(M) であり、共用体検索フェーズの場合は O(Ma(m)) です。合計で O(Ma(m)) です。

Prim アルゴリズムの場合。ヒープを使用する必要はありません。重みごとに 1 つずつ、7 つのリスト/キュー/配列/その他 (一定時間の挿入と取得) が必要です。そして、最も安い発信エッジを探しているときは、これらのリストの 1 つが (最も安いものから) 空でないことを確認し、そのエッジを使用します。7 は定数なので、アルゴリズム全体が O(M) 時間で実行されます。

于 2012-05-28T08:53:08.103 に答える
2

私が理解しているように、宿題に答えるのは一般的ではありませんが、これはあなただけでなく他の人にも役立つことを願っています;)

堅苦しい：

Prim は、Kruskal と同様に、最小スパニング ツリー (MST) を見つけるためのアルゴリズムです。アルゴリズムを視覚化する簡単な方法は、紙にグラフを描くことです。次に、選択したすべてのノードに移動可能な線 (カット) を作成します。以下の例では、セット A がカット内のノードになります。次に、カットを通過する最小のエッジを選択しました。つまり、ラインの内側のノードから外側のノードまでです。重みが最小のエッジを常に選択します。新しいノードを追加した後、カットを移動して、新しく追加されたノードが含まれるようにします。次に、すべてのノードがカット内に収まるまで繰り返します。

アルゴリズムの簡単な要約は次のとおりです。

  1. 選択した頂点を含むセット A を作成します。最初は、ユーザーが選択したランダムな開始ノードが含まれています。
  2. 別のセット B を作成します。これは最初は空で、選択したすべてのエッジをマークするために使用されます。
  3. エッジ E (u, v)、つまりノード u からノード v へのエッジを選択します。エッジ E は、集合 A 内にノード u があり、v が A 内にない最小の重みを持つエッジでなければなりません。 (重みが等しいエッジが複数ある場合は、いずれかをランダムに選択できます)。
  4. セット B にエッジ (u, v) を追加し、セット A に v を追加します。
  5. A = V になるまで手順 3 と 4 を繰り返します。ここで、V はすべての頂点の集合です。
  6. セット A と B はスパニング ツリーを表します。MST には A 内のノードが含まれ、B はそれらの接続方法を記述します。

クラスカル:

Kruskal は Prim に似ていますが、カットがない点が異なります。したがって、常に最小のエッジを選択します。

  1. 最初は空のセット A を作成します。選択したエッジを保存するために使用されます。
  2. セット E から最小の重みを持つエッジ E を選択しますが、これはまだ A にはありません。(u,v) = (v,u) であるため、エッジを 1 方向にのみトラバースできます。
  3. A に E を追加します。
  4. A と E が等しくなるまで、つまりすべてのエッジを選択するまで、2 と 3 を繰り返します。

これらのアルゴリズムの正確なパフォーマンスについては確信が持てませんが、Kruskal は O(E log E) であり、Prim のパフォーマンスは、エッジを格納するために使用するデータ構造に基づいていると想定しています。バイナリ ヒープを使用すると、最小エッジの格納に隣接行列を使用する場合よりも、最小エッジの検索が高速になります。

お役に立てれば！

于 2012-05-28T08:51:18.993 に答える