﻿ Tips And Tutorial - Presented by Oneous!

Minimum Spanning Tree (MST) Problem: Kruskal's Algorithm
Last Update: 20 March, 2009

Problem: Kruskal's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

My Code:

``````// C++ code : Minimum Spanning Tree (MST) - Kruskal Algorith

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAX(a,b)  ((a>b)?a:b)
#define CLEAR(A,N)  (memset(A,0,(N)*sizeof(A)))

/****** Kruskal Algorithm  ********************************
***********************************************************/
const int maxEdgeSize=200005; // size of maximum edg
typedef struct{
int x,y,cost;
}graph;

graph v[maxEdgeSize];
int ar[maxEdgeSize];

int findSet(int i) {
while(ar[i]!=i)
i=ar[i];
return i;
}

void makeUnion(int a, int p1,int b, int p2) {
int x=MAX(p1,p2);
ar[a]=x;
ar[b]=x;
ar[p1]=x;
ar[p2]=x;
}

int adjustUsingUnionFind(int a, int b){ // return 1 if previously a and b were not in same set, else
if(ar[a]==-1) {
ar[a]=a;
}
if(ar[b]==-1) {
ar[b]=b;
}

int p1=findSet(a);
int p2=findSet(b);

if(p1!=p2){
makeUnion(a,p1,b,p2);
return 1;
}else {
return 0;
}
}

// compare function for sort(
bool operator < (graph a, graph b){
return a.cost < b.cost;
}

/**********End of Kruskal Algorithm ********************
********************************************************/

int main() {
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)

int m,n,i,minimumCost;

while(scanf("%d %d",&m,&n)==2){ // n is the number of edge, m is the number of Nod
if(m==0&&n==0)
break;

// Take Input every edge with cost between x and y node in Grap
for(i=0;i<n;i++){
scanf("%d %d %d",&v[i].x,&v[i].y,&v[i].cost);
}

// sort according to edge valu
sort(v,v+n);

// CLEAR the array ar[
for(i=0;i<m;i++)
ar[i]=-1;

// Now, take each Edge and adjust it with cos
minimumCost=0;
for(i=0;i<n;i++){
minimumCost+=v[i].cost;
}

printf("%d\n",minimumCost);
}

// End of main function.......
return 0;
}

/***  Programmed by:
###########################
##   ORONNO   #############