Prims Algorithmus mit Priorität Warteschlange

Question

So schrieb ich Prim-Algorithmus in Java, mit manuell erstellten calsses und ArrayList's. Aber ich wurde gebeten, eine Prioritätswarteschlange zu implementieren, und ich verstehe nicht wirklich, wie das funktionieren soll, ich habe mir Beispiele angesehen und es scheint irgendwie so zu sein, wie ich es an erster Stelle geschrieben habe. Mein Code:

public class Edge { 
private int d = 0; 
private int t = 10000; 
private int nr = 0; 

public Edge() { 

} 

public int getD() { 
    return this.d; 
} 

public void setD(int d) { 
    this.d = d; 
} 

public int getT() { 
    return this.t; 
} 

public void setT(int t) { 
    this.t = t; 
} 

public int getNr() { 
    return this.nr; 
} 

public void setNr(int nr) { 
    this.nr = nr; 
} 

public String toString() { 
    return String.format(d + " " + t + " " + nr); 
} 

}

public class Paths { 
private int L; 
private int C; 

public Paths(int L, int C) { 
    this.L = L; 
    this.C = C; 
} 

public int getL() { 
    return this.L; 
} 

public int getC() { 
    return this.C; 
} 

}

private final static int[] lst = {0, 0, 3, 5, 8, 11, 16, 18, 19, 20}; 
private static ArrayList<Paths> v = new ArrayList<Paths>(); 
private static ArrayList<Edge> edge = new ArrayList<Edge>(); 
private static final int start = 5; 
private static int orderNr = 1; 
/** 
* @param args the command line arguments 
*/ 
public static void main(String[] args) { 
    test(); 
} 

private static void test() { 
    fillV(); 
    edge.get(start).setD(orderNr); 
    edge.get(start).setT(0); 
    edge.get(start).setNr(0); 
    prim(); 
    print(); 
} 

private static void prim() { 
    while(check()) { 
     for(int i = 1; i < edge.size(); i++) { 
      if(edge.get(i).getD() == orderNr) { 
       int boundary1 = lst[i] + 1; 
       int boundary2 = lst[i + 1]; 
       for(int j = boundary1; j <= boundary2; j++) { 
        if(edge.get(v.get(j).getL()).getT() > v.get(j).getC() && edge.get(v.get(j).getL()).getD() == 0) { 
         edge.get(v.get(j).getL()).setT(v.get(j).getC()); 
         edge.get(v.get(j).getL()).setNr(i); 
        } 
       } 
      } 
     } 
     int min = 20000; 
     int index = 0; 
     for(int i = 1; i < edge.size(); i++) { 
      if(edge.get(i).getT() < min && edge.get(i).getD() == 0) { 
       min = edge.get(i).getT(); 
       index = i; 
      } 
     } 
     orderNr++; 
     edge.get(index).setD(orderNr); 
    } 
} 

private static boolean check() { 
    for(int i = 1; i < edge.size(); i++) { 
     if(edge.get(i).getD() == 0) { 
      return true; 
     } 
    } 
    return false; 
} 

private static void print() { 
    for(int i = 1; i < edge.size(); i++) { 
     System.out.println(edge.get(i).toString()); 
    } 
} 

}

ich nicht meine v Arraylist Schöpfung enthalten, wie es manuelle .add Methode war, immer und immer wieder nochmal. Wenn jemand tatsächlich detailliertes Material zur Prioritätswarteschlange hat, wäre ich mehr als glücklich.

Answer 1

Überprüfen Sie diese anderen question.

Zusammenfassend wird die Prioritätswarteschlange die Effizienz Ihrer Implementierung verbessern, indem die Auswahl des Scheitelpunkts mit der Mindestentfernung vereinfacht wird. Derzeit iterieren Sie über Ihre Kanten, um dieses Minimum zu finden (also überprüfen Sie sie alle jedes Mal, was vermieden werden kann).

Wie Wikipedia weist darauf hin, können Sie Ihre Zeit Komplexität von O (V^2) zu O (V + E log (V)) reduzieren, wobei V die Menge der Eckpunkte in Ihrem Diagramm ist und E ist die Menge der Kanten.

Obwohl der Algorithmus, den Sie in den Beispielen gesehen haben, Ihrem vielleicht ähnlich ist (schließlich ist es immer noch Prims Algorithmus), erhalten Sie mit einer Prioritätswarteschlange eine schnellere Implementierung (zumindest für große Graphen) .

Dies ist ein Beispiel für die Wichtigkeit der Wahl der richtigen Datenstruktur: Während der Algorithmus und das Ergebnis gleich sind, kann die Zeitkomplexität erheblich variieren.