Advertisement
Oppenheimer

Prims algo MST

Jul 15th, 2023
166
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define V 6
  6.  
  7. //Selects the vertex which has the least weight edge of all unselected vertices.
  8. int selectMinVertex(vector<int> &value, vector<bool>& setMST){
  9.     int minimum = INT_MAX;
  10.     int vertex;
  11.     for(int i = 0; i < V; i++){
  12.         if(setMST[i] == false && value[i] < minimum){
  13.             vertex = i;
  14.             minimum = value[i];
  15.         }
  16.     }
  17.     return vertex;
  18. }
  19.  
  20. //Print the minimum spanning tree
  21. void printMst(int[] parent, int graph[V][V]){
  22.     cout << "Src.\tDest.\tWeight\n";
  23.     for(int i = 1; i < parent.length; i++){
  24.             cout << i << "\t" << parent[i] << "\t" << graph[i][parent[i]] << "\n";
  25.     }
  26. }
  27.  
  28. void findMST(int graph[V][V]){
  29.     int parent[V];
  30.     vector<int> value(V, INT_MAX);
  31.     vector<bool> setMST(V, false);
  32.  
  33.     parent[0] = -1;
  34.     value[0] = 0;
  35.  
  36.         //Iterate through all the vertices of the graph
  37.     for(int i = 0; i < V-1; i++){
  38.                 /** from all vertices connecting the currently chosen vertices,
  39.                 * select a vertex which adds minimum edge
  40.                 **/
  41.         int U = selectMinVertex(value, setMST);
  42.         setMST[U] = true;
  43.                 /**
  44.                 * Add newly added vertex as parent of all the vertices
  45.                 * it connects to except those that are already chosen.
  46.                 * This would help us print the tree later.
  47.                 **/
  48.         for(int j = 0; j < V; j++){
  49.             if(graph[U][j] != 0 && setMST[j] == false && graph[U][j] < value[j]){
  50.                 value[j] = graph[U][j];
  51.                 parent[j] = U;
  52.             }
  53.         }
  54.     }
  55.     printMst(parent, graph);
  56. }
  57.  
  58.  
  59. int main(){
  60.         /**
  61.         * This is the adjacency matrix representation of graph where
  62.         * the weight for the edge i,i is stored in ith row and jth column
  63.         * **/
  64.     int graph[V][V] = {
  65.         {0, 4, 6, 0, 0, 0},
  66.         {4, 0, 6, 3, 4, 0},
  67.         {6, 6, 0, 1, 8, 0},
  68.         {0, 3, 1, 0, 2, 3},
  69.         {0, 4, 8, 2, 0, 7},
  70.         {0, 0, 0, 3, 7, 0},
  71.     };
  72.     findMST(graph);
  73.     return 0;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement