Реализация алгоритма Прима

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, который содержит значение ключа (которое, как я полагаю, является самым легким ребром, подключенным к Node) и родительский узел. Моя проблема в том, что я не понимаю, как добавить узел в очередь с приоритетами. Добавление всех узлов в очередь с приоритетом не имеет смысла для меня, когда для родителя установлено значение NIL, а для ключа ∞.

Answer 1

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

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

Answer 2

, если вы не хотите использовать PriorityQueue, здесь - моя реализация Heap в 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++];}
    }
}

Answer 3

Вам не нужно беспокоиться о добавлении всех узлов в очередь с приоритетами, даже если они имеют бесконечные ключи; в конечном итоге они будут понижены на DECREASE_KEY в последней строке вашего псевдокода. В любом случае вам понадобится эта операция, поэтому нет причин не упрощать вашу жизнь и не вставлять их сразу.

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