プリムのアルゴリズムの実装

Question

私のCSクラスでは、プリムのアルゴリズムをJavaで実装する必要があり、プライオリティキューのステップに問題があります。私は優先順位キューの経験があり、一般的に動作することを理解していますが、特定のステップに問題があります。

Prim(G,w,r) 
    For each u in V[G] 
    do key[u] ← ∞ 
     π[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) 

私は親ノード（私はノードに接続されている最軽量のエッジであると仮定）のキー値が含まれているNodeクラスを作成しました。私の問題は、ノードを優先度キューに追加することを理解できないことです。優先度キューにすべてのノードを追加しても、親がNILに設定され、キーが∞に設定されているときは私には意味をなさない。

Answer 1

無限のキーがあってもすべてのノードを優先度キューに追加する必要はありません。彼らは最終的にあなたの擬似コードの最後の行でDECREASE_KEYによって下げられます。あなたはこの操作をとにかく必要とするので、あなたの人生を単純化して一度にそれらを挿入しない理由はありません。

あなたの擬似コードには、切断されたグラフで奇妙な動作をする問題が1つしかありません。

Answer 2

質問の疑似コードでは、key[u]とπ[u]は、アルゴリズムが完了したときにGの最小スパニングツリーを表す値のセットです。値はアルゴリズム開始時にそれぞれ∞とNILに初期化され、MSTにまだ頂点が追加されていないことを示します。次のステップでは、ルート要素（key[r] ← 0）を設定します。

優先キューQは、keyとπとは別のデータ構造です。 Qは、元のグラフのすべての頂点で初期化する必要があります。G、はキーの値ではなく、πです。 Qから抽出した各頂点に隣接するすべての頂点を知る必要があるため、各頂点の最も明るいエッジおよび親ノードより多くの情報が必要であることに注意してください。

Answer 3

もしあなたがPriorityQueueを使いたくないなら、hereは私のHeap in Javaの実装です。あなたはMinHeapでPriorityQueueを置き換えることができます。

package algo2; 

import java.io.DataInputStream; 
import java.io.InputStream; 
import java.util.HashMap; 
import java.util.Map; 
import java.util.PriorityQueue; 

public class Prims { 

private static final class GNode implements Comparable<GNode> { 
    // unique id of the node 
    int id; 

    // map of child nodes and their respective distance from current node 'id' 
    Map<GNode, Integer> children = new HashMap<GNode, Integer>(); 

    // used in future computation, to store minimal/optimal updated distance 
    int distFromParent=0; 

    public GNode(int i) { 
     this.id=i; 
    } 

    @Override 
    public int compareTo(GNode o) { 
     return this.distFromParent-o.distFromParent; 
    } 

    @Override 
    public String toString() { 
     return "GNode [id=" + id + ", distFromParent=" + distFromParent 
       + "]"; 
    } 
} 

static long findLengthOfMST(GNode[] nodes) { 
    PriorityQueue<GNode> pq = new PriorityQueue<GNode>(); 
    boolean[] visited = new boolean[nodes.length]; 
    boolean[] exited = new boolean[nodes.length]; 
    pq.add(nodes[1]); 
    visited[1] = true; 
    long sum = 0; 
    int count = 0; 
    while (pq.size() > 0) { 
     GNode o = pq.poll(); 
     if (!exited[o.id]) { 
      for (GNode n : o.children.keySet()) { 
       if (exited[n.id]) { 
        continue; 
       } 
       if (visited[n.id]) { 
        if (n.distFromParent >= o.children.get(n)) { 
         n.distFromParent = o.children.get(n); 
        } 
       } else { 
        visited[n.id] = true; 
        n.distFromParent = o.children.get(n); 
        pq.add(n); 
       } 
      } 
      sum += o.distFromParent; 
      exited[o.id] = true; 
      count++; 
     } 
     if (pq.size() == 0) { 
      for (int i = 1; i < nodes.length; i++) { 
       if (!exited[i]) { 
        pq.add(nodes[i]); 
       } 
      } 
     } 
    } 
    System.out.println(count); 
    return sum; 
} 

public static void main(String[] args) { 
    StdIn s = new StdIn(System.in); 
    int V = s.nextInt(); 
    int E = s.nextInt(); 
    GNode[] nodes = new GNode[V+1]; 
    for (int i = 0; i < E; i++) { 
     int u = s.nextInt(); 
     int v = s.nextInt(); 
     GNode un = nodes[u]; 
     GNode vn = nodes[v]; 
     if (un == null) { 
      un = new GNode(u); 
      nodes[u] = un; 
     } 
     if (vn == null) { 
      vn = new GNode(v); 
      nodes[v] = vn; 
     } 

     int w = s.nextInt(); 
     un.children.put(vn, w); 
     vn.children.put(un, w); 
    } 
    long len = findLengthOfMST(nodes); 
    System.out.println(len); 
} 

private static class StdIn { 
    final private int BUFFER_SIZE = 1 << 17; 
    private DataInputStream din; 
    private byte[] buffer; 
    private int bufferPointer, bytesRead; 
    public StdIn(InputStream in) { 
    din = new DataInputStream(in); 
    buffer = new byte[BUFFER_SIZE]; 
    bufferPointer = bytesRead = 0; 
    } 
    public int nextInt() {int ret = 0;byte c = read();while (c <= ' ')c = read();boolean neg = c == '-';if (neg)c=read();do{ret=ret*10+c-'0';c = read();} while (c>' ');if(neg)return -ret;return ret;} 
    private void fillBuffer(){try{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);}catch(Exception e) {}if(bytesRead==-1)buffer[0]=-1;} 
    private byte read(){if(bufferPointer == bytesRead)fillBuffer();return buffer[bufferPointer++];} 
    } 
}