Prim’s MST (Minimum Spanning Tree)

Given a graph with N nodes and M edges (Undirected) with positive weights. Find the minimum spanning tree. A tree with minimum overall weight edge. This is cover all nodes of the original graph if possible. You will be given a starting point S. Just in case the graph is not connected. Then you can find the MST which contains S.

 

Input Format

First line has two integers , denoting the number of nodes in the graph and , denoting the number of edges in the graph.

The next lines each consist of three space separated integers , first two integers are the two nodes between which the  edge exists, last/third integer is the weight of the edge.

The last line has an integer , denoting the starting node.

Nodes are numbered from 1 to N.

There can be multiple edges between same pair of nodes. Consider them as multiple edges.

 

Sample input:

3 3
1 2 2
1 3 3
3 2 6
1

Sample Output

5

 

Solution:

</pre>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct edge{
int begin;
int end;
int weight;
};
//minHeap
bool comp(const edge& a, const edge& b){
return (a.weight > b.weight);
}

void print(edge e){
cout<<e.begin<<" -> "<<e.end<<" w: "<<e.weight<<endl;
}
void prims(vector <vector <edge> > &adj, int start, int V){
vector <edge> minHeap;
int result = 0;
for(int i = 0; i < adj[start].size(); i++){
minHeap.push_back(adj[start][i]);
//print(adj[start][i]);
}
make_heap (minHeap.begin(),minHeap.end(), comp);
vector <bool> visited(V);
visited[start] = true;
while(!minHeap.empty()){
edge e = minHeap.front();
//cout<<"popped ";
//print(e);
pop_heap(minHeap.begin(), minHeap.end(),comp);
minHeap.pop_back();
if(!visited[e.end]){
visited[e.end] = true;
result += e.weight;
//cout<<"res: "<<result<<endl;
for(int i = 0; i < adj[e.end].size(); i++){
minHeap.push_back(adj[e.end][i]); push_heap(minHeap.begin(), minHeap.end(), comp);
//cout<<"push ";
//print(adj[e.end][i]);
}
}
}
cout<<result<<endl;
}

int main() {
int V, E, S;
cin>>V;
cin>>E;
vector <vector <edge> > adj(V);
for(int i = 0; i < E; i++){
int start, end, weight;
cin>>start;
cin>>end;
cin>>weight;
start--;end--;
edge e1;
e1.end = end;
e1.weight = weight;
e1.begin = start;
adj[start].push_back(e1);
edge e2;
e2.end = start;
e2.weight = weight;
e2.begin = end;
adj[end].push_back(e2);
}
cin>>S;
S--;
prims(adj,S, V);
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s