Tuesday, August 2, 2016

Kruskal's algorithm

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

struct node{
    int s;
    int e;
    int weight;
};

int makeset(int a[],int e){
    for(int i=0;i<=e;i++)\
        a[i]=i;
    return a[e];
}
int found(int arry[], int x){
    if(x==arry[x])
        return x;
    return found(arry, arry[x]);
}
int Union(int arry[],int x,int y){
    if(x!=y)
        arry[y]=x;
}

bool compare(node a, node b){
    if(a.weight<b.weight)
        return true;
    else
        return false;
}

int main(){

    int i, totalEdge, totalNode, p1, p2, w;
    node edgeList[50];
    cout << "How many vertices?  " ;
    cin>>totalNode;
    cout << "How many edges?  " ;
    cin>>totalEdge;

    for(i=0;i<totalEdge;i++){
        cin>>p1;
        cin>>p2;
        cin>>w;

        edgeList[i].s = p1;
        edgeList[i].e = p2;
        edgeList[i].weight = w;
        edgeList[i].s = p2;
        edgeList[i].e = p1;
    }
    sort(edgeList,edgeList+totalEdge, compare);
    int arry[totalEdge];
    makeset(arry,totalEdge);

    int total=0;
    for(int i=0; i<totalEdge; i++){
        int x=found(arry, edgeList[i].s);
        int y=found(arry, edgeList[i].e);
        if(x!=y){
            Union(arry,x,y);
            total+=edgeList[i].weight;
            cout << edgeList[i].s << " " << edgeList[i].e << " " << edgeList[i].weight << endl;
        }
    }
    cout<< total<<endl;


    return 0;
}

No comments:

Post a Comment