Prima Minimum Spanning Tree

Question

Я пытаюсь оптимизировать график, используя алгоритм Min Spanning Tree Prim. Но я не получаю желаемого ответа.

Алгоритм:

1. Construct min heap array. The array consists of nodes which have a vertex value 
and a key value. The key values are initialized to INT_MAX initially. 

2. Make the zeroth node's key 0, as this is the starting node. 

3. I iterate over the heap, till it becomes empty, and in every step following is done: 
    - Extract the minimum element out of the min heap. This is done by extractMin() 
     function in the class MinHeap. 

4. Look for this extracted element's neighbors and update their keys based on the weight of 
the corresponding edge. 

5. Then decrease the key value in the minHeap by using decreaseKey() function in 
class MinHeap. 

6. Store the parent and child for which the condition satisfies in a map called parent. 

Это описание Код:

1. The code contains two header files, Graph.h and MinHeap.h. The functions are all std f 
functions in these files. So there won't be any problem in understanding them. 

2. The Graph.cpp file contains the PrimMST() function which does all the job and performs 
the entire algorithm. 

Вот проблема:

1. When I extract a node from heap in PrimMST() function, I call extractMin() function 
defined in MinHeap.cpp file. This function swaps the top most node in the heap with the 
bottom most node. And then performs the heapify operation. 


But, it is not performing this operation though I have called it in extractMin(). There's 
no problem with minHeapify function which does the heapify operation as it does 
perform its job else where is the program. 

Это график, который я пытаюсь оптимизировать:

Это программа: P.S .: Я размещаю весь код со всеми файлами заголовка, чтобы его можно было легко понять. Но пропустите код и, пожалуйста, обратите внимание на функцию PrimMST() в файле Graph.cpp.

/***************GRAPH.H*******************************/ 

#ifndef GRAPH_H_ 
#define GRAPH_H_ 
#include <list> 
#include <map> 

using namespace std; 

class AdjListNode{ 
    int v; 
    int weight; 
public: 
    AdjListNode(int _v, int _w){ v = _v; weight = _w; } 
    int getV()  { return v; } 
    int getWeight() { return weight; } 
}; 

class Graph{ 
    int V;       // To store number of vertices in the graph 
    list<AdjListNode> *adj; // This is a map for storing the adjacency list 
    map<int,int> mapping;   // A map to form a dictionary of vertex values to their array indexes for look ups. 
    map<int,int> parent;   // A map to store the parent child for a given edge in the graph 
public: 
    Graph(int);      // Class constructor 
    void HashTable(int *, int);  // This method uses the map library in STL to create a mappinh 
            // of arbitrary integers to zero based array indexes 
    int getHashedElt(int);   // This method returns the value corresponding to a given 
            // key in a hash table 
    void addEdge(int, int, int); // This method adds the second arg to the adj list of first arg. 
    void printGraph();    // This method prints the adjacency list of all the vertices 

    void PrimMST(int *, int);  // This function will perform the Prim's MST algorithm and optimize 
            // the number of nodes in the graph 

}; 
#endif 

/****************GRAPH.CPP*************************/ 
#include <iostream> 
#include <climits> 
#include <list> 
#include <map> 
#include "Graph.h" 
#include "MinHeap.h" 

#define INF 9999 

using namespace std; 

Graph::Graph(int v){ 
    V = v; 
    adj = new list<AdjListNode>[V]; 
} 

// This function takes in a pointer to array and its size as its arguments to create a hashtable. 
// So. if you have 10,11,12,13,14,15 as the nodes. 
// Create an array int arr[] {10,11,12,13,14,15}, and int size = sizeof(arr)/sizeof(arr[0]) 
// And pass it to this function this creates a dictionary named mapping for O(1) look up of 
// index by other functions. 
void Graph::HashTable(int *nodeData, int size){ 
    for (int i = 0; i < size; i++){ 
      mapping[nodeData[i]] = i; 
    } 
    return; 
} 


// This method returns the value corresponding to a particular node in constant time. 
int Graph::getHashedElt(int data){ 
    return mapping[data]; 
} 

// This function creates an adjacency list for every vertex in the graph 
void Graph::addEdge(int node1, int node2, int weight){ 
    AdjListNode node(node2, weight); 
    int index = getHashedElt(node1); 
    adj[index].push_back(node); 
} 


void Graph::printGraph(){ 
    list<AdjListNode>::iterator j; 
    int i = 0; 
    while (i<V){ 
      for (j = adj[i].begin(); j != adj[i].end(); j++){ 
        cout <<"(" << j->getV() << "," << j->getWeight() << ")->"; 
      } 
      if (!adj[i].empty()) 
        cout << "NULL\n"; 
      i++; 
    } 
} 

void Graph::PrimMST(int *arr, int size){ 
    MinHeap minHeap(arr,size); 
    size_t key[V]; // Key values to pick minimum weight edge in cut 

    for (int i = 1; i < V; i++){ 
      parent[arr[i]] = -1; // All the parents are -1 initially 
      key[i] = INT_MAX;  // Initially all the keys are initialised to positive infinity 
      MinHeapNode *newNode = minHeap.newMinHeapNode(arr[i],key[i]); 
      //cout << "("<< arr[i] << ", " << key[i] << ")\n"; 
      minHeap.insertNode(i, newNode); 
    } 

    // Make key value of 0th vertex as 0 so that it is extracted first. 
    key[0] = 0; 

    // This function insertNode creates a newNode with vertex number and associated key value. 
    MinHeapNode *newNode = minHeap.newMinHeapNode(arr[0],key[0]); 
    minHeap.insertNode(0, newNode); 

    //minHeap.printHeap(); 

while (!minHeap.isEmpty()){ 
      // Extract the vertex with minimum key value 
      minHeap.printHeap(); 
      MinHeapNode *minNode = minHeap.extractMin(); 
      // Get the vertex of this minNode. 
      int u = minNode->v; 
      cout << "\n"; 
      minHeap.printHeap(); 
      cout << "\n\n\n"; 
      //cout << u << "\n"; 
      // Traverse through all the adjacent vertices of u (extended vertex) 
      // and update their key values 
      list<AdjListNode>::iterator j; 
      for (j = adj[mapping[u]].begin(); j != adj[mapping[u]].end(); j++) { 
        int v = j->getV(); 
        // If v is not yet included in the MST and weight of u-v 
        // is less than key value of v, then update key value 
        // and parent of v 
        if (minHeap.isInMinHeap(v) && j->getWeight() < key[mapping[v]]){ 
          key[mapping[v]] = j->getWeight(); 
    //      cout << key[mapping[v]] << "\n"; 
          parent[v] = u; 
          minHeap.decreaseKey(v,key[mapping[v]]); 
        } 
      } 
    } 
    for (int k = 1; k < size; k++){ 
      //cout <<parent[arr[k]]<<"---"<<arr[k]<< "\n"; 
    } 
    return; 
} 


/*************MINHEAP.H**************************/ 
#ifndef MINHEAP_H_ 
#define MINHEAP_H_ 
#include <map> 

using namespace std; 

struct MinHeapNode{ 
    int v; 
    size_t key; 
}; 

class MinHeap{ 
    int size;    // Number of heap nodes present in the heap at any given time 
    int capacity;   // Capacity of min heap 
    map<int,int> pos;  // This is map which stores the array index of a given vertex, for O(1) look up 
    MinHeapNode **MinHeapArray;  // This array containe pointers to all the heap nodes. 

public: 
    MinHeap(int*,int);  // Class constructor, it will allocate space to minHeap and initialise all the variables. 
          // It also creates the map of every vertex to an index, so that there is O(1) look up. 
    MinHeapNode *newMinHeapNode(int,size_t); // This function creates a new min heap node with a given value of vertex and weight 
    int getIndex(int);      // This function returns the index of a given vertex in pos map. 
    void insertNode(int,MinHeapNode *);    // This function inserts a node into the MinHeapArray. 
    void printHeap(); 
    void swapMinHeapNode(MinHeapNode **, MinHeapNode **); // It will perform swap operation in the heap. 
    void minHeapify(int);  // Standard function to heapify at given idx. 
    bool isEmpty();   // A utility function to check whether given heap is empty or not. 
    bool isInMinHeap(int); // Checks whether given vertex in the heap or not 
    MinHeapNode *extractMin();  // Std func to extract to minimum node from the heap. 
    void decreaseKey(int,int);  // This func performs the decreaseKey op by making use of pos map. 

}; 

#endif 


/***************MINHEAP.CPP***************************/ 
#include <iostream> 
#include <cstdlib> 
#include <climits> 
#include <map> 
#include "MinHeap.h" 

using namespace std; 

MinHeap::MinHeap(int *arr,int s){ 
    size = 0; 
    capacity = s; 
    MinHeapArray = (MinHeapNode **)malloc(sizeof(MinHeapNode *)*s); 
    for (int i = 0; i < s; i++){ 
      pos[arr[i]] = i;  // This is a mapping from vertex to array index i. This will enable O(1) access of any var in heap. 
    } 
} 

MinHeapNode *MinHeap::newMinHeapNode(int v, size_t key){ 
    MinHeapNode *node = new MinHeapNode; 
    node->v = v; 
    node->key = key; 
    return node; 
} 

int MinHeap::getIndex(int v){ 
    return pos[v]; 
} 

void MinHeap::insertNode(int idx, MinHeapNode *node){ 
    MinHeapArray[idx] = node; 
    size++; 
} 

bool MinHeap::isEmpty(){ 
    return size == 0; 
} 

bool MinHeap::isInMinHeap(int v){ 
    if (pos[v] < size) 
      return true; 
    return false; 
} 


void MinHeap::printHeap(){ 
    for (int i = 0; i < size; i++){ 
      cout << MinHeapArray[i]->v << ", "<< MinHeapArray[i]->key << "\n"; 
    } 
} 

void MinHeap::swapMinHeapNode(MinHeapNode **a, MinHeapNode **b){ 
    MinHeapNode *t = *a; 
    *a = *b; 
    *b = t; 
} 

// A standard function to heapify at given index idx 
// This function also updates position of nodes when they are swapped. 
void MinHeap::minHeapify(int idx){ 
    int smallest, left, right; 
    left = (2*idx + 1); 
    right = (2*idx + 2); 
    smallest = idx; 

    if (left < size && MinHeapArray[left]->key < MinHeapArray[smallest]->key) 
      smallest = left; 
    if (right < size && MinHeapArray[right]->key < MinHeapArray[smallest]->key) 
      smallest = right; 
    if (smallest != idx){ 
      // To nodes to be swapped in min heap 
      MinHeapNode *smallestNode = MinHeapArray[smallest]; 
      MinHeapNode *idxNode = MinHeapArray[idx]; 

      // Change the mapping of vertices in pos map. 
      pos[smallestNode->v] = idx; 
      pos[idxNode->v] = smallest; 

      // Swap Nodes using swapMinHeapNode utility function 
      MinHeap::swapMinHeapNode(&smallestNode, &idxNode); 
      minHeapify(smallest); 
    } 
    return; 
} 

MinHeapNode *MinHeap::extractMin(){ 
    if (isEmpty()) 
      return NULL; 

    // Store the root node 
    MinHeapNode *root = MinHeapArray[0]; 

    // Replace the root with last node 
    MinHeapNode *lastNode = MinHeapArray[size-1]; 
    MinHeapArray[0] = lastNode; 

    // Update position of last node 
    pos[root->v] = size - 1; 
    pos[lastNode->v] = 0; 

    // Reduce heap size and heapify root 
    size--; 
    MinHeap::minHeapify(0); 

    return root; 
} 

void MinHeap::decreaseKey(int v, int key){ 
    // Get the index of v in heap array 
    int i = pos[v]; 

    // Get the node and update its key value 
    MinHeapArray[i]->key = key; 

    // Travel up till the complete tree is not heapified. 
    // This is O(logn) loop 
    while (i && MinHeapArray[i]->key < MinHeapArray[(i-1)/2]->key){ 
      // Swap this node with its parent 

      // First update the pos matrix 
      pos[MinHeapArray[i]->v] = (i-1)/2; 
      pos[MinHeapArray[(i-1)/2]->v] = i; 

      // Do the swapping now. 
      MinHeap::swapMinHeapNode(&MinHeapArray[i], &MinHeapArray[(i-1)/2]); 

      // move to the parent index in the next iteration 
      i = (i - 1)/2; 
    } 
    return; 
} 



/**********************MAIN FUNCTION CALL***************/ 
#include <iostream> 
#include "Graph.h" 
#include "MinHeap.h" 

using namespace std; 

int main(){ 
    int arr[] = {0,1,2,3,4,5,6,7,8};  // An array with all the vertices 
    int size = sizeof(arr)/sizeof(arr[0]); 

    Graph g(size); 
    g.HashTable(arr,size); 
    g.addEdge(0, 1, 4); 
    g.addEdge(0, 7, 8); 
    g.addEdge(1, 2, 8); 
    g.addEdge(1, 7, 11); 
    g.addEdge(2, 3, 7); 
    g.addEdge(2, 8, 2); 
    g.addEdge(2, 5, 4); 
    g.addEdge(3, 4, 9); 
    g.addEdge(3, 5, 14); 
    g.addEdge(4, 5, 10); 
    g.addEdge(5, 6, 2); 
    g.addEdge(6, 7, 1); 
    g.addEdge(6, 8, 6); 
    g.addEdge(7, 8, 7); 
    //g.printGraph(); 
    g.PrimMST(arr,size); 
    return 0; 
} 

С этим вводом я получаю ошибочный выход. Обратите внимание, что этот вывод получается путем вызова printHeap до и после вызова extractMin(). И как можно видеть, хотя minHeapify (0) вызывается в extractMin() каждый раз, когда узел извлекается. Это как-то не выполняет операцию и, следовательно, куча не heapified, что приводит к ошибочному результату Пример вывода, для первых 3 итераций:

First Iteration: 

0, 0 
1, 2147483647 
2, 2147483647 
3, 2147483647 
4, 2147483647 
5, 2147483647 
6, 2147483647 
7, 2147483647 
8, 2147483647 

8, 2147483647 
1, 2147483647 
2, 2147483647 
3, 2147483647 
4, 2147483647 
5, 2147483647 
6, 2147483647 
7, 214748364 


Second Iteration: 
1, 4 
7, 8 
2, 2147483647 
8, 2147483647 
4, 2147483647 
5, 2147483647 
6, 2147483647 
3, 2147483647 

3, 2147483647 
7, 8 
2, 2147483647 
8, 2147483647 
4, 2147483647 
5, 2147483647 
6, 2147483647 

Third Iteration: 
2, 8 
7, 8 
3, 2147483647 
8, 2147483647 
4, 2147483647 
5, 2147483647 
6, 2147483647 

6, 2147483647 
7, 8 
3, 2147483647 
8, 2147483647 
4, 2147483647 
5, 2147483647 

Обратите внимание на второй и третьей итерации, это не heapified вообще, даже если я вызвал функцию minHeapify в функции extractMin() в конце.

Мне отчаянно нужна помощь в этом.

Answer 1

ваша проблема в этой строке MinHeap::swapMinHeapNode(&smallestNode, &idxNode); в minHeapify(int idx) вы обмениваетесь указатели на узлы, которые не своп значения в MinHeapArray вы должны поменять местами элементы массива, а не так, эта строка должна быть заменена MinHeap::swapMinHeapNode(&MinHeapArray[idx], &MinHeapArray[smallest]);