6

私の質問が話すように、プリムのアルゴリズムで優先キューを使用する理由を知りたいですか? 単純な方法を使用することからどのように私たちを救うのですか (はい、聞いたことがありますが、理由はわかりません)。

adjacency list について順を追って説明できる人がいれば、とてもうれしいです。コーメンの本を使用しています。

疑似コード:

Prim(G,w,r) //what is w (weight?) and r?
  For each u in V[G]
    do key[u] ← ∞ // what is key?
       π[u] ← NIL  
  key[r] ← 0
  Q ← V[G]  
  While Q ≠ Ø
    do u ← EXTRACT-MIN(Q)
       for each v in Adj[u]
            if v is in Q and w(u,v) < key[v]
                 then π[v] ← u
                       key[v] ← w(u,v)

std::vector を使用してから std::make_heap(); を使用することを考えています。エッジを格納するための優先キューとして。

4

4 に答える 4

11

プリムのアルゴリズムには、「最も近い」頂点を取得する必要があるステップがあります。通常の配列を使用する場合、このステップには O(N) のコストがかかりますが、優先キュー (ヒープなど) を使用する場合は O(logN) しかかかりません。

したがって、優先キューを使用する理由は、アルゴリズムの時間の複雑さを軽減することです (つまり、プログラムの実行が速くなります)。

**

アップデート：

**

ウィキペディアからのプリムのアルゴリズムの説明は次のとおりです。太字の部分は、私が話した最も近い頂点を見つけるための部分です。

入力: 頂点 V とエッジ E を持つ空でない接続された重み付きグラフ (重みは負の値にすることができます)。

初期化: Vnew = {x}、x は V からの任意のノード (開始点)、Enew = {}

Vnew = V になるまで繰り返します: u が Vnew にあり、v がそうでない最小の重みを持つエッジ (u, v) を選択します (同じ重みを持つエッジが複数ある場合は、それらのいずれかを選択できます)。v を Vnew に追加します。および (u, v) を Enew に

出力: Vnew と Enew は最小スパニング ツリーを記述します

于 2011-08-12T11:08:49.367 に答える
6

あなたはそれを「必要」としません。実際、プリムのアルゴリズムの素朴な実装は、距離の配列の線形検索を実行して、次に近い頂点を見つけるだけです。ダイクストラのアルゴリズムはまったく同じように機能します。

人々がそれを使用する理由は、アルゴリズムの実行時間を大幅に短縮するためです。O(V^2 + E)からに変わりO(E*log(V))ます。

その鍵となるのはEXTRACT-MIN(Q)関数です。単純に行うと、この操作に時間がかかりO(V)ます。ヒープを使用すると、時間がかかりますO(logV)。

于 2011-08-12T12:03:50.533 に答える
4

これを大まかにメモリから実行するため、少し一貫性がない可能性がありますが、要点は次のとおりです。

class Graph
  Set<node> nodes;   // The set of nodes in the graph
  MultiMap<Node, Edge> edges; // Map from Node, to a list of weighted edges connected to the node. If it weren't weighted, any spanning tree by definition would be a minimum spanning tree.

Graph Prim(Graph input):
   Graph MST = new Graph();
   PriorityQueue<Edge> candidateEdges;
   Node anyNode = input.pickAnyNodeAtRandom()
   candidateEdges.putAll(input.edges.get(anyNode));

   while MST.nodes.size() < input.nodes.size():
      edge = candidateEdges.takeLowest()  // THIS IS THE IMPORTANT PART         
      if edge.v1 in MST.nodes and edge.v2 not in MST.nodes:
         MST.nodes.add(edge.v2)       
         MST.edges.add(edge)
         candidateEdges.add(edge.v2.edges)

基本的に、アルゴリズムの各ステップで、部分最小スパニングツリーに1つの頂点があり、ツリーに1つの頂点がない最小エッジを探し、そのエッジをツリーに追加します。それをどのように効率的に行いますか？部分スパニングツリーの頂点に接続されているすべてのエッジを効率的に並べ替える方法がある場合は、許容できる頂点を持つエッジが見つかるまで、それらを単純に繰り返すことができます。

このような順序付けられたデータ構造がないと、最小値を直接効率的に取得するのではなく、最小値を見つけるために毎回すべての候補エッジを反復処理する必要があります。

于 2011-08-15T02:46:07.190 に答える