Skip to content

Instantly share code, notes, and snippets.

@MagallanesFito
Created April 20, 2017 06:03
Show Gist options
  • Save MagallanesFito/8d556d1f6f6a8e4b375e3fa5076ff8cf to your computer and use it in GitHub Desktop.
Save MagallanesFito/8d556d1f6f6a8e4b375e3fa5076ff8cf to your computer and use it in GitHub Desktop.
Prim's algorithm in C++ from geeksforgeeks.org
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef pair<int,int> iPair;
class Graph{
int V;
//lista de adyacencia con pesos
//list<int> *adj; sin pesos
list <pair<int,int> > *adj;
public:
Graph(int V);
void addEdge(int u,int v,int w);
void primMST();
};
Graph::Graph(int V){
this->V = V;
adj = new list<iPair>[this->V];
}
void Graph::addEdge(int u,int v,int w){
//Para lista de adyacencia es (label,peso)
adj[u].push_back(make_pair(v,w));
adj[v].push_back(make_pair(u,w));
}
void Graph::primMST(){
//Priority Queue (PQ) es (peso,label)
//Implementa un MIN HEAP de iPair
priority_queue<iPair,vector<iPair>,greater<iPair> > pq;
int src = 0;
vector<int> key(V,INF);
vector<int> parent(V,-1);
vector<bool> inMST(V,false);
pq.push(make_pair(0,src));
key[src] = 0;
while(!pq.empty()){
int u = pq.top().second;
pq.pop();
inMST[u] = true;
list<pair<int,int> >::iterator it;
for(it = adj[u].begin();it!=adj[u].end();it++){
int v = (*it).first;
int weight = (*it).second;
if(!inMST[v] && key[v] > weight){
key[v] = weight;
pq.push(make_pair(key[v],v));
parent[v] = u;
}
}
}
for(int i=1;i<V;i++){
cout << parent[i] << " - " << i << endl;
}
}
int main(){
int V = 5;
Graph g(V);
g.addEdge(0,1,3);
g.addEdge(0,2,2);
g.addEdge(1,2,1);
g.addEdge(1,3,4);
g.addEdge(2,4,1);
g.addEdge(3,4,2);
g.primMST();
return 0;
}
@Sourav-1234
Copy link

Sir well done can you just do it without writing the custom struct method ok

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment