Advertisement
spider68

Prims Algo. minimum spaning tree

Jan 17th, 2021
174
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int spanningTree(int V, int E, vector<vector<int>> &graph);
  4. // Driver code
  5.  
  6. int main() {
  7.     int t;
  8.     cin >> t;
  9.     while (t--) {
  10.         int V, E;
  11.         cin >> V >> E;
  12.         vector<vector<int> > graph(V, vector<int>(V, 0));
  13.         int i=0;
  14.         while (i++<E) {
  15.             int u, v, w;
  16.             cin >> u >> v >> w;
  17.             u--, v--;
  18.             graph[u][v] = w;
  19.             graph[v][u] = w;
  20.         }
  21.  
  22.         cout << spanningTree(V, E, graph) << endl;
  23.     }
  24.     return 0;
  25. }
  26. // } Driver Code Ends
  27.  
  28. typedef pair<int, int> PII;
  29. // Function to construct and print MST for
  30. // a graph represented using adjacency
  31. // matrix representation, with V vertices.
  32. // graph[i][j] = weight if edge exits else INT_MAX
  33. bool visited[1000+1];
  34.  
  35. int prim(vector<PII> adj[]){
  36.     priority_queue<PII, vector<PII>, greater<PII> > pq;
  37.     int minCost = 0;
  38.     PII p;
  39.     pq.push({0,1});
  40.     while(!pq.empty())
  41.     {
  42.         p=pq.top();
  43.         pq.pop();
  44.         int x = p.second;
  45.         if(visited[x])
  46.             continue;
  47.         minCost += p.first;
  48.         visited[x] = true;
  49.         for(int i=0; i<adj[x].size(); i++)
  50.         {
  51.             int y = adj[x][i].second;
  52.             if(!visited[y])
  53.                 pq.push(adj[x][i]);
  54.         }
  55.     }
  56.     return minCost;
  57. }
  58.  
  59. int spanningTree(int V, int E, vector<vector<int>> &graph) {
  60.     // code here
  61.    
  62.     for(int i=0; i<=V; i++)
  63.         visited[i] = 0;
  64.     vector<PII> adj[V+1];
  65.    
  66.     for(int i=0; i<V; i++)
  67.     {
  68.         for(int j=i; j<V; j++)
  69.         {
  70.             if(graph[i][j] != 0)
  71.             {
  72.                
  73.                 adj[i+1].push_back(make_pair(graph[i][j],j+1));
  74.                 adj[j+1].push_back(make_pair(graph[i][j],i+1));
  75.             }
  76.         }
  77.     }
  78.     return prim(adj);
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement