SHARE
TWEET

Untitled

a guest Jun 24th, 2019 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdlib.h>
  2. #include <iostream>
  3. #include "AdjacencyMatrix.h"
  4.  
  5. void Prim(Matrix, int, int);
  6. int main() {
  7.     Matrix M(6);
  8.     int weight = 0;
  9.     Prim(M,weight,0);
  10.     system("pause");
  11.     return 0;
  12. }
  13. void Prim(Matrix*G, int*D, int s) { // Prim’s MST algorithm
  14. int VISITED = 1;
  15. int UNVISITED = 0;
  16. int V[6];                 // Store closest vertex
  17. int i, w;
  18. for (int i=0; i<G->n(); i++)       // Initialize
  19.     D[i] = INFINITY;
  20. D[s] = 0;
  21. for (i=0; i<G->n(); i++) {         // Process the vertices
  22.     int v = minVertex(G, D);
  23.     G->setMark(v, VISITED);
  24.     //if (v != s)
  25.     //  AddEdgetoMST(V[v], v);         // Add edge to MST
  26.     if (D[v] == INFINITY) return;    // Unreachable vertices
  27.     for (w=G->first(v); w<G->n(); w = G->next(v,w))
  28.         if (D[w] > G->weight(v,w)) {
  29.             D[w] = G->weight(v,w);       // Update distance
  30.             V[w] = v;                    // Where it came from
  31.         }
  32.     }
  33. }
  34.      
  35. class Matrix : public Graph {
  36. public:
  37.     Matrix (int numVert) { Init(numVert); }
  38.     ~Matrix() {       // Destructor
  39.         delete [] mark; // Return dynamically allocated memory
  40.         for (int i=0; i<numVertex; i++)
  41.             delete [] matrix[i];
  42.         delete [] matrix;
  43.     }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top