Start New Discussion within our **Software Development Community** Answered # C++ code for Kruskal Algorithm

Featured Reply Grunt 19 Featured Reply andor 25 Featured Reply ~s.o.s~ 2,560 zandiago 115 rachnaa er.chiraggupta happyuk naamurad

1

It's a pretty simple algorithm. Didn't you find anything about it in your algorithm's book?

You can start from here

http://en.wikipedia.org/wiki/Kruskal's_algorithm

1

I don't think that someone will provide you the source code. Try at google. I bet that you will find something

1

Post your attempt and we will definately help you out on topics on where you got stuck. Just giving out the source code would do you more harm than good.

0

smart_pallav....welcome aboard.I reccommend taking a look at the Rules & FAQ for the daniweb forum. Please do not re-open old threads...You must start your own thread and post what you've come up with for us to help...we don't do assignments for students!

0

plz mail me d java codes for prim's , kruskal's nd single source shortest path algorithms.

my id is *<< email id snipped >>*

0

hi below is the krushkal algorithm code

it uses UNIONFIND data structure

code starts :

```
/*Krushkal Algorithm
Input defined as follow
First give number of nodes n
starting end of edge and then ending end of edge and then cost of edge
example:
graph is as follows
1-2 2-5 3-4 4-2 2-3
then
input is
5
1 2 1
2 5 1
3 4 1
4 2 1
2 3 1
0 to end the input
*/
#define N 100 //N is max nodes
#define M 10000 // M is max edges
#include<iostream>
#include <stdlib.h>
using namespace std;
// UNION FIND DATA STRUCURE STARTS
struct data{
int name;
int size;
struct data *home;
};
typedef struct data mydata;
class makeunionfind
{
public :
mydata S[N];
public:
makeunionfind(int n)
{
for(int i=0;i<n;i++)
{
S[i].name=i+1;
S[i].size=0;
S[i].home=&S[i];
}
}
void myunion(int a, int b)
{
int sizea,sizeb;
sizea=S[a-1].home->size;
sizeb=S[b-1].home->size;
if(sizea>sizeb)
{
(S[b-1].home)->home=S[a-1].home;
S[a-1].size=sizea+sizeb;
}
else
{
(S[a-1].home)->home=S[b-1].home;
S[b-1].size=sizea+sizeb;
}
}
int myfind(int a)
{
mydata *temp,*temp2,*stoppoint;
int result;
temp2=&S[a-1];
temp=S[a-1].home;
while(temp2!=temp)
{
temp2=temp;
temp=(*temp2).home;
}
result=temp2->name;
stoppoint=temp2;
temp2=&S[a-1];
//path compression
do{
temp=temp2->home;
(*temp2).home=stoppoint;
temp2=temp;
}while(temp2!=stoppoint);
return result;
}
};
//UNION FIND DATA STRUCURE ends
//Krushkal Algo starts
struct node{
int name;
};
typedef struct node mynode;
class edge
{
public :
mynode *start,*end;
double cost;
edge()
{
start=NULL;
end=NULL;
cost=0;
}
};
struct edges{
edge e;
};
int compare(const void *a,const void *b )
{
edge *a1,*b1;
a1=(edge*)a;
b1=(edge*)b;
if(a1->cost<b1->cost)
return -1;
else if (a1->cost>b1->cost)
return 1;
else
return 0;
}
void *kruskal(edge *e,int n,int m,int *size,edge *ans)
{
makeunionfind list(n);
int (*comp)(const void *a,const void *b );
int k=0;
comp=compare;
qsort((void*)e,m,sizeof(e[0]),comp);
for(int i=0;i<m;i++)
{
int s,f;
s=(e[i].start)->name;
f=(e[i].end)->name;
if(list.myfind(s)==list.myfind(f))
{
continue;
}
else
{
list.myunion(s,f);
ans[k]=e[i];
k++;
}
}
*size=k;
return ans;
}
int main()
{
mynode nodes[N];
edge e[M];
int n,m; // n is the number of nodes , m is no. of nodes
cin>>n;
for(int i=0;i<n;i++){
nodes[i].name=i+1;
}
// temp1 is starting node temp2 is ending node temp3 is cosr
int temp1,i;
cin>>temp1;
for (i=0;temp1!=0;i++)
{
int temp2;
double temp3;
cin>>temp2;
cin>>temp3;
e[i].start=&nodes[temp1-1];
e[i].end=&nodes[temp2-1];
e[i].cost=temp3;
cin>>temp1;
}
m=i;
edge ans[M];
int size;
kruskal(e,n,m,&size,ans);
for(int p=0;p<size;p++)
{
cout<<p+1<<") start "<<(ans[p].start)->name<<" end "<<(ans[p].end)->name<<endl;
}
return 0;
}
```

Above works perfectly fine :)

And is good implementation

If you want to know about unionfind data structure search google please

0

I know of two links you may be interested in.

- An ordinary C++ implementation of Kruskal's algorithm
- A C++/MFC tool with graphical user interface to add network nodes and links etc

and calculate the Kruskal minimal spanning tree via the Boost libraries

-1

hi all... you have asked question 7 years ago.. back then i did not even know what programing is.. today I do. Today I am going to give you exact answer as you were expacting at the time of posting this question... simply visit the following link and have code for Kruskel Algorithm in C++

http://in.docsity.com/en-docs/Kruskals_Algorithm_-_C_plus_plus_Code

This question has already been answered. Start a new discussion instead.