0
In Prim-Algorithmus, wird empfohlen, die invariant in der folgenden Art und Weise zu erhalten:Heap Aktualisierung in beiden Richtungen (Prim-Algorithmus)
When a vertice v is added to the MST:
For each edge (v,w) in the unexplored tree:
1. Delete w from the min heap.
2. Recompute the key[w] (i.e. it's value from the unexplored tree
to the explored one).
3. Add the value back to the heap.
Also, im Grunde diese Streichung aus dem Heap beinhaltet (und heapify die O nimmt (log n)) und dann wieder einsetzen (wieder O (log n))
Stattdessen, wenn ich die folgende Methode verwenden:
For each edge (v,w) in the unexplored tree:
1. Get the position of the node in the heap(array) using HashMap -> O(1)
2. Update the value in place.
3. Bubble up or bubble down accordingly. -> O(logn)
Welche bessere Konstanten als die vorherige gibt.
Der umstrittene Teil ist der dritte Teil, in dem Im sollte nach oben oder unten sprudeln.
Meine Implementierung ist wie folgt:
public int heapifyAt(int index){
// Bubble up
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
// Bubble down
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
return index;
}
Und Ich bin aus dem Haufen Rupfen auf diese Weise:
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF; // set this to infinity, so it'll be at the bottom
// of the heap.
heapifyat(0);
visited.add(minNodeNumber);
updatevertices(minNodeNumber); // Update the adjacent vertices
return toRet;
}
Und die Eckpunkte so gerupft Aktualisierung:
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){ // Skip the nodes that are already visited
int positionInHeap = map.get(adjacentNode.nodeNumber); // Retrive the position from HashMap
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
heap[positionInHeap].edgeCost = adjacentNode.edgeCost; // Update if the cost is better
heapifyAt(positionInHeap); // Now this will go bottom or up, depending on the value
}
}
}
}
Aber wenn ich es in großen Graphen ausführe, schlägt der Code fehl. Es gibt kleine Werte im unteren Teil des Heaps und groß Werte an der Spitze. Aber die heapifyAt() API scheint gut zu funktionieren. Ich kann also nicht herausfinden, ob mein Ansatz falsch oder mein Code ist? Darüber hinaus, wenn ich ersetzen die HeapifyAt() API von SiftDown(), dh den Heap erstellen, funktioniert es gut, aber es macht keinen Sinn aufrufen SiftDown(), O (n) Zeit für jede Updates, die verarbeitet werden können in logarithmischer Zeit.
Kurz gesagt: Ist es möglich, die Werte in Heap in beide Richtungen zu aktualisieren, oder der Algorithmus falsch ist, da es deshalb empfohlen wird, das Element zuerst aus Heap zu entfernen und es erneut einzufügen.
EDIT: Vollständiger Code:
public class Graph1{
public static final int INF = 9999999;
public static final int NEGINF = -9999999;
static class AdjNode{
int nodeNumber;
int edgeCost;
AdjNode next;
AdjNode(int nodeNumber, int edgeCost){
this.nodeNumber = nodeNumber;
this.edgeCost = edgeCost;
}
}
static class AdjList implements Iterable<AdjNode>{
AdjNode head;
AdjList(){
}
public void add(int to, int cost){
if(head==null){
head = new AdjNode(to, cost);
}else{
AdjNode temp = head;
while(temp.next!=null){
temp = temp.next;
}
temp.next = new AdjNode(to, cost);
}
}
public Iterator<AdjNode> iterator(){
return new Iterator<AdjNode>(){
AdjNode temp = head;
public boolean hasNext(){
if(head==null){
return false;
}
return temp != null;
}
public AdjNode next(){
AdjNode ttemp = temp;
temp = temp.next;
return ttemp;
}
public void remove(){
throw new UnsupportedOperationException();
}
};
}
public void printList(){
AdjNode temp = head;
if(head==null){
System.out.println("List Empty");
return;
}
while(temp.next!=null){
System.out.print(temp.nodeNumber + "|" + temp.edgeCost + "-> ");
temp = temp.next;
}
System.out.println(temp.nodeNumber + "|" + temp.edgeCost);
}
}
static class Heap{
int size;
AdjNode[] heap;
Graph g;
int pluckSize;
Set<Integer> visited = new HashSet<Integer>();
HashMap<Integer, Integer> map = new HashMap<>();
Heap(){
}
Heap(Graph g){
this.g = g;
this.size = g.numberOfVertices;
this.pluckSize = size - 1;
heap = new AdjNode[size];
copyElements();
constructHeap();
}
public void copyElements(){
AdjList first = g.list[0];
int k = 0;
heap[k++] = new AdjNode(0, NEGINF); //First entry
for(AdjNode nodes : first){
heap[nodes.nodeNumber] = nodes;
}
for(int i=0; i<size; i++){
if(heap[i]==null){
heap[i] = new AdjNode(i, INF);
}
}
}
public void printHashMap(){
System.out.println("Priniting HashMap");
for(int i=0; i<size; i++){
System.out.println(i + " Pos in heap :" + map.get(i));
}
line();
}
public void line(){
System.out.println("*******************************************");
}
public void printHeap(){
System.out.println("Printing Heap");
for(int i=0; i<size; i++){
System.out.println(heap[i].nodeNumber + " | " + heap[i].edgeCost);
}
line();
}
public void initializeMap(){
for(int i=0; i<size; i++){
map.put(heap[i].nodeNumber, i);
}
}
public void swap(int one, int two){
AdjNode first = heap[one];
AdjNode second = heap[two];
map.put(first.nodeNumber, two);
map.put(second.nodeNumber, one);
AdjNode temp = heap[one];
heap[one] = heap[two];
heap[two] = temp;
}
public void constructHeap(){
for(int i=size-1; i>=0; i--){
int temp = i;
while(heap[temp].edgeCost < heap[(int)Math.floor(temp/2)].edgeCost){
swap(temp, (int)Math.floor(temp/2));
temp = (int)Math.floor(temp/2);
}
}
initializeMap();
}
public void updatevertices(int pluckedNode){
for(AdjNode adjacentNode : g.list[pluckedNode]){
if(!visited.contains(adjacentNode.nodeNumber)){
int positionInHeap = map.get(adjacentNode.nodeNumber);
if(adjacentNode.edgeCost < heap[positionInHeap].edgeCost){
// //System.out.println(adjacentNode.nodeNumber + " not visited, Updating vertice " + heap[positionInHeap].nodeNumber + " from " + heap[positionInHeap].edgeCost + " to " + adjacentNode.edgeCost);
// heap[positionInHeap].edgeCost = INF;
// //heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
// int heapifiedIndex = heapifyAt(positionInHeap); // This code follows my logic
// heap[heapifiedIndex].edgeCost = adjacentNode.edgeCost; // (which doesnt work)
// //heapifyAt(size - 1);
heap[positionInHeap].edgeCost = adjacentNode.edgeCost;
//heapifyAt(positionInHeap);
constructHeap(); // When replaced by SiftDown,
} // works as charm
}
}
}
public void printSet(){
Iterator<Integer> it = visited.iterator();
System.out.print("Printing set : [");
while(it.hasNext()){
System.out.print((int)it.next() + ", ");
}
System.out.println("]");
}
public AdjNode pluck(){
AdjNode min = heap[0];
int minNodeNumber = heap[0].nodeNumber;
AdjNode toRet = new AdjNode(min.nodeNumber, min.edgeCost);
heap[0].edgeCost = INF;
constructHeap();
visited.add(minNodeNumber);
updatevertices(minNodeNumber);
return toRet;
}
public int heapifyAt(int index){
if(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
while(heap[index].edgeCost < heap[(int)Math.floor(index/2)].edgeCost){
swap(index, (int)Math.floor(index/2));
index = (int)Math.floor(index/2);
}
}else{
if(index*2 + 2 < size){
while(index*2 + 2 < size && (heap[index].edgeCost > heap[index*2 + 1].edgeCost|| heap[index].edgeCost > heap[index*2 + 2].edgeCost)){
if(heap[index*2 + 1].edgeCost < heap[index*2 + 2].edgeCost){
//swap with left child
swap(index, index*2 + 1);
index = index*2 + 1;
}else{
//swap with right child
swap(index, index*2 + 2);
index = index*2 + 2;
}
}
}
}
return index;
}
}
static class Graph{
int numberOfVertices;
AdjList[] list;
Graph(int numberOfVertices){
list = new AdjList[numberOfVertices];
for(int i=0; i<numberOfVertices; i++){
list[i] = new AdjList();
}
this.numberOfVertices = numberOfVertices;
}
public void addEdge(int from, int to, int cost){
this.list[from].add(to, cost);
this.list[to].add(from, cost);
}
public void printGraph(){
System.out.println("Printing Graph");
for(int i=0; i<numberOfVertices; i++){
System.out.print(i + " = ");
list[i].printList();
}
}
}
public static void prims(Graph graph, Heap heap){
int totalMin = INF;
int tempSize = graph.numberOfVertices;
while(tempSize>0){
AdjNode min = heap.pluck();
totalMin += min.edgeCost;
System.out.println("Added cost : " + min.edgeCost);
tempSize--;
}
System.out.println("Total min : " + totalMin);
}
public static void main(String[] args) throws Throwable {
Scanner in = new Scanner(new File("/home/mayur/Downloads/PrimsInput.txt"));
Graph graph = new Graph(in.nextInt());
in.nextInt();
while(in.hasNext()){
graph.addEdge(in.nextInt() - 1, in.nextInt() - 1, in.nextInt());
}
Heap heap = new Heap(graph);
prims(graph, heap);
}
}
Aktualisieren Sie die Knotenpositionszuordnung in swap()? – user158037
Ja, das tue ich. Wird den Code in einiger Zeit aktualisieren –
@MayurKulkarni Ich glaube, dass Sie einige Dinge über die Frage aktualisieren müssen, damit wir Ihr Problem besser überprüfen können. Die Definition von AdjNode, die Deklaration von Heap, einige Fehler verursachende Eingaben (zumindest die Beschreibung davon) sowie die von Ihnen getroffene Fehlererklärung fehlen in Ihrer Frageanweisung, und beide sind möglicherweise notwendig, um Ihre Implementierung vollständig zu verstehen. – ilim