Реализация алгоритма Prim's

Question

Для моего класса CS мне нужно реализовать алгоритм Prim в 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 в последней строке вашего псевдокода. В любом случае вам понадобится эта операция, поэтому нет причин не упрощать вашу жизнь и вставлять их все сразу.

Я вижу только одну проблему с вашим псевдокодом, а именно, что она будет вести себя странно на отключенных графиках.

Answer 2

В псевдокоде в вашем вопросе key[u] и π[u] - это набор значений, который будет представлять минимальное остовное дерево G, когда алгоритм закончен. Значения инициализируются в ∞ и NIL соответственно в начале алгоритма, чтобы показать, что в MST еще не добавлены вершины. Следующий шаг устанавливает корневой элемент (key[r] ← 0).

Очередь приоритета Q - это отдельная структура данных от key и π. Q должен быть инициализирован всеми вершинами в исходном графе G, не значениями в ключе и π. Обратите внимание, что вам понадобится больше информации, чем просто самый легкий край и родительский узел для каждой вершины, так как вам нужно знать все вершины, смежные с каждым из выбранных из Q.

Answer 3

Если вы не хотите использовать PriorityQueue, here - это моя реализация кучи на Java. Вы можете заменить 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++];} 
    } 
}