Thursday, 24 January 2013

kruskal algorithm code snippet of MST

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
#include<utility>
using namespace std;
vector< pair< pair < int,int > ,int > > edge,ans;   //edge x,y,weight
map< int, vector<int> > group;    //groupno --> groupelement
vector<int> node(1001,0);   //number of nodes maximum 1000;
bool comp(pair< pair <int,int > ,int > A,pair< pair <int ,int > ,int > B)
{
    if(A.second< B.second)
        return true;
    else
        return false;
}
int main()
{
    int cgroup=1,m;
    int n,x,y,w,e=0;
    cin>>n>>m;  //m - no of nodes
    for(int i=0;i<n;i++)
    {

        cin>>x>>y>>w;
        edge.push_back(make_pair(make_pair(x,y),w));

    }

    sort(edge.begin(),edge.end(),comp);
    int k=0;
    while(e<n-1)
    {
        x=edge[k].first.first,y=edge[k].first.second,w=edge[k].second;
        if(node[x]==0&&node[y]==0)
        {
              ans.push_back(make_pair(make_pair(x,y),w));
                      group[cgroup].push_back(x);
              group[cgroup].push_back(y);
              node[x]=cgroup;
              node[y]=cgroup;
              cgroup++;
              e++;
        }
        else if(node[x]!=0&&node[y]!=0)
        {
                    if(node[x]>node[y])
                          {
                  ans.push_back(make_pair(make_pair(x,y),w));

                  e++;
                  int tempgrp=node[y];
                  node[y]=node[x];
                        for(int i=0;i<group[tempgrp].size();i++)
                  {
                      int elem=group[tempgrp][i];
                      node[elem]=node[x];
                      group[node[x]].push_back(elem);
                  }
               
                }
            else if(node[x]<node[y])
            {
                ans.push_back(make_pair(make_pair(x,y),w));

                e++;
                int tempgrp=node[x];
                node[x]=node[y];
                for(int i=0;i<group[tempgrp].size();i++)
                {
                    int elem=group[tempgrp][i];
                    node[elem]=node[y];
                    group[node[y]].push_back(elem);
                }
           
            }
        }
        else if(node[x]!=0&&node[y]==0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[x];
            group[tempgrp].push_back(y);
            node[y]=node[x];
        }
        else if(node[x]==0&&node[y]!=0)
        {
            ans.push_back(make_pair(make_pair(x,y),w));

            e++;
            int tempgrp=node[y];
            node[x]=node[y];
            group[tempgrp].push_back(x);
        }

             k++;
    }
    int grp=node[1];
    for(int i=0;i<ans.size();i++)
        cout<<ans[i].first.first<<" "<<ans[i].first.second<<" "<<ans[i].second<<endl;
       


}

No comments:

Post a Comment