Kruskal’s Minimum Spanning Tree Algorithm

Standard

Kruskal’s algorithm is the best and probably fastest option if you’re urging to form a subgraph of a graph connecting all nodes. Some implementations are shown.

Minimum Spanning Tree
To form an MST(Minimum Spanning Tree) follow this procedure,

1. Begin with a connected graph G.
2. E is the set of all edges of different weights, from G.
3. Sort edges of E in the ascending order of their weights.
4. Go through each member(edge) of E and see if the nodes of that edge is already connected or not.
5. If they aren’t connected, connect them and include that member of E(edge) int MST.
6. Continue this process untill you’ve got n-1 edges(in case of n nodes).

An implementation in C++ using Disjoint Set data structure, is shown

#include <cstdio>
#include <algorithm>
#define MAX_node 100000
using namespace std;

struct edg{
	int a,b,w;
	bool operator < (const edg &b) const{
		return w<b.w;
	}
}E[MAX_node+1];

int Prev[MAX_node+1];
int parent(int a){
	if(a==Prev[a]) return a;
	return Prev[a]=parent(Prev[a]);
}

int main(){
	int node,edge;
	while(scanf("%d%d",&node,&edge)){
		
		int TOTAL=0;
			
		for(int i=1;i<=node;i++) Prev[i]=i;//*
		for(int i=0;i<edge;i++) scanf("%d%d%d",&E[i].a,&E[i].b,&E[i].w);//**
		
		sort(E,E+edge);//***
		
		for(int i=0; i<edge; i++ ){
			int u=parent(E[i].a);//****
			int v=parent(E[i].b);
			
			if(u!=v){
				TOTAL+=E[i].w;
				Prev[u]=v;//*****
			}
		}
		
		printf("Total Cost of MST %d\n",TOTAL);
	}
	return 0;
}

/*
 * Making each node it's own parent
 ** Input edges in the format "node1 node2 weight"
 *** Sorting them in the ascending order of weight
 **** Find the current parent of a and b
 ***** If the nodes of that edge is not connected yet, Connect them.
 */

if you don’t know Maximum possible number of nodes, then just use a vector(which is a bit slower) of type ‘edg’.

Related Problems
MST(spoj)
Dark Roads(UVa)
Audiophobia(UVa)
Connect the Campus(UVa)
Highways(UVa)



Maximum Spanning Tree
To get a maximum spanning tree, the procedure is almost same. The only difference is that, you got to sort members of E in the descending order of their weights.

Related Problems
Heavy Cargo(UVa)



Second Best Minimum Spanning Tree
There may be some other better procedure to find the second best MST, but this is the one I’ve used.
1. First form an MST of graph G, and mark the edges which formes the MST.
2. Then for each member edge of the MST, Form another MST without using that particular member.
3. Thus, u need to form n-1 (in case of n nodes) ‘another’ MSTs and consider the minimun among them.

Related Problems
Is There A Second Way Left ?(UVa)
ACM contest and Blackout(UVa)

atod function

Standard

Add to DiggAdd to FaceBookAdd to Google BookmarkAdd to MySpaceAdd to Twitter
atod function’s work is identical to atoi‘s. But this one is for doubles

// for texting/ example purposes
#include <iostream> // for cout and endl
#include <cmath> // for pow
using namespace std; // so we don't have to do std::coud or std::endl
//end testing/ example purposes 

char* substr(char* str, int start, int end){
	char* a = new char[1+(end-start)]; // we need a new char array for the return
	for(int i=start; i<end; i++){ // loop through the string
		a[i-start] = str[i]; // set the characters in the new char array to those from the old one compensating for the substring
	}
	a[end-start] = '\0'; // add the null character, so we can output
	return a; // return
}

double atod(char* a){
	double retVal = atoi(a); // start off getting the number, assuming it is a valid string to use atoi on.
	int start = 0;
	int end = 0;
	for(int i=0; a[i] != '\0'; i++){ // loop through the string to find the positions of the decimal portion, if there is one
		if(a[i] == '.' && start == 0){
			start = i+1; // set the start position to 1 more than the current (avoids a char as the first character - we want a digit)
		}
		else if(start != 0 &&  (a[i] < '0' || a[i] > '9')){ // make sure that start is set and that we aren't looking at digits
			end = i; // if so, set the end location for the substring
			break; // we don't need to continue anymore - break out of the loop
		}
	}
	if(end > start){ // avoids substring problems.
		char* decimal = substr(a, start, end); // get the string that is after the decimal point
		int dec = atoi(decimal); // make it an integer
		int power = end-start; // find the power of 10 we need to divide by
		retVal += ((double)dec)/(pow(10.0, (double)power)); // divide and add to the return value (thus making it a true double)
	}
	return retVal; // return - simple enough
}

// for testing/ example purposes
int main(){
	cout << atod("127.02501 test") << endl; // test it out on a valid character stream
	return 0;
}
// end testing/ example purposes