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).

Resource: Click Here

 

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[0])))


/****** 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++){
			if(adjustUsingUnionFind(v[i].x, v[i].y)==1)
				minimumCost+=v[i].cost;
		}

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

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

/***  Programmed by:
###########################
##   ORONNO   #############
## Team-:"DU-Gladiator"  ##
## CSEDU 12th Batch.  #####
###########################
Note: This program is not totally
useless. Because, at least, this
might be used as a bad example!!!!
**********************************/