My Weblog

Blog about programming and math

Algorithm to find out minimum spannig tree

Given a connected, undirected graph, a spanning tree of that graph is a subgraph which is a tree and connects all the vertices together. A single graph can have many different spanning trees. We can also assign a weight to each edge, which is a number representing how unfavorable it is, and use this to assign a weight to a spanning tree by computing the sum of the weights of the edges in that spanning tree. A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

Prim’s Implimentation.

#include<cstdio>
#include<vector>
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int,int> PI;
int n,m;
bool vis[10009];
vector<PI> V[10009],E;
priority_queue<PI,vector<PI>,greater<PI> >Q;
int main()
{

int u,v,w,cost;
while(scanf(“%d%d”,&n,&m)==2)
{
memset(vis,0,sizeof(vis));
cost=0;
for(int i=0;i<10009;i++)
V[i].clear(),E.clear();
for(int i=0;i<m;i++)
scanf(“%d%d%d”,&u,&v,&w),V[u-1].push_back(PI(w,v-1)),V[v-1].push_back(PI(w,u-1));
vector<int> D(n,INT_MAX),P(n);
D[0]=0;
P[0]=0;
Q.push(PI(0,0));
while(!Q.empty())
{
PI tmp=Q.top();
Q.pop();
u=tmp.second;
w=tmp.first;
if(vis[u]) continue;
vis[u]=1;
cost+=w;
for(int i=0;i<V[u].size();i++)
{
v=V[u][i].second,w=V[u][i].first;
if(w<D[v] && !vis[v])
D[v]=w,Q.push(PI(w,v)),P[v]=u;
//printf(“v=%d w=%d\n”,v,w);

}
}
for(int i=1;i<n;i++)
printf(“%d->%d\n”,P[i]+1,i+1);
cout<<cost<<endl;
}

}

Kruskal Implimentation

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int,int> PI;
typedef pair<int,PI> PII;
vector<PII> V;
int N,E,P[10009],R[10009];

int _Find_Set(int x)
{
if(x!=P[x]) P[x]=_Find_Set(P[x]);
return P[x];
}
void _Merge_Set(int x,int y)
{
int Px=_Find_Set(x),Py=_Find_Set(y);
if(R[Px]>R[Py]) P[Py]=Px;
else P[Px]=Py;
if(R[Px]==R[Py]) R[Py]=R[Py]+1;
}

int main()
{
int u,v,w;
while(scanf(“%d%d”,&N,&E)==2)
{
V.clear();
for(int i=0;i<E;i++)
scanf(“%d%d%d”,&u,&v,&w),V.push_back(make_pair(w,make_pair(u-1,v-1)));

sort(V.begin(),V.end());
/*for(int i=0;i<E;i++)
cout<<V[i].second.first+1<<” “<<V[i].second.second+1<<” “<<V[i].first<<endl;
cout<<endl;*/
for(int i=0;i<N;i++)
P[i]=i,R[i]=0;

int sum=0;
for(int i=0;i<E;i++)
{
int x=_Find_Set(V[i].second.first),y=_Find_Set(V[i].second.second);
if(x!=y) _Merge_Set(x,y),sum+=V[i].first/*,printf(“merging %d and %d  weight=%d\n”,x+1,y+1,V[i].first)*/;
}
cout<<sum<<endl;

}

}

Advertisements

November 8, 2008 - Posted by | Programming

No comments yet.

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

%d bloggers like this: