Prim의 알고리즘 구현

Question

내 CS 클래스의 경우 Java의 Prim 알고리즘을 구현해야하며 우선 순위 대기열 단계에 문제가 있습니다. 우선 순위 대기열에 대한 경험이 있으며 일반적으로 작동하는 것으로 이해하지만 특정 단계에서 문제가 있습니다.

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) 

키 값 (노드에 연결된 가장 밝은 가장자리라고 가정)과 부모 노드가 포함 된 노드 클래스를 만들었습니다. 내 문제는 우선 순위 큐에 노드를 추가하는 것을 이해하지 못한다는 것입니다. 우선 순위 큐에 모든 노드를 추가해도 부모가 NIL로 설정되고 키가 ∞로 설정되면 나에게 의미가 없습니다.

Answer 1

키가 무한하더라도 모든 노드를 우선 순위 큐에 추가 할 필요가 없습니다. 그들은 결국 DECREASE_KEY에 의해 의사 코드의 마지막 줄에서 낮아질 것입니다. 어쨌든이 작업이 필요하므로 삶을 단순화하고 한 번에 모두 삽입하지 않아도됩니다.

의사 코드에 단 하나의 문제 만 표시됩니다. 즉, 연결되지 않은 그래프에서 이상하게 작동합니다.

Answer 2

질문의 의사 코드에서 key[u] 및 π[u]은 알고리즘 완료시 G의 최소 스패닝 트리를 나타내는 값 집합입니다. 이 값은 알고리듬의 시작 부분에 각각 ∞과 NIL으로 초기화되어 MST에 아직 정점이 추가되지 않았 음을 나타냅니다. 다음 단계는 루트 요소 (key[r] ← 0)를 설정합니다.

우선 순위 큐 Q은 key 및 π과는 별도의 데이터 구조입니다. Q은 원래 그래프의 모든 정점으로 초기화해야합니다 G, 키 및 π의 값이 아닙니다. Q에서 추출한 각 꼭지점에 인접한 모든 꼭지점을 알아야하기 때문에 각 꼭지점의 가장 밝은 가장자리와 부모 노드보다 많은 정보가 필요합니다.

Answer 3

PriorityQueue를 사용하지 않으려면 here을 자바에서 힙 구현 ... PriorityQueue를 MinHeap으로 바꿀 수 있습니다.

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++];} 
    } 
}