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.

Recommended Articles

```
Try
Dim cn As New SqlConnection("Data Source=MSR\LOCAL;Initial Catalog=Eventena;Integrated Security=True")
cn.Open()
Using cmd As New SqlClient.SqlCommand("INSERT into BirthdayRegistration where Name='" & TextBox4.Text & "',LastName='" & TextBox2.Text & "',Email='" & TextBox5.Text & "',StreetNo='" & TextBox6.Text & "',Main='" & TextBox7.Text & "',Area='" & TextBox8.Text & "',City='" & ComboBox1.Text & "',State='" & ComboBox2.Text & ...
```

Hi,

I am facing an issue in string to const char pointer conversion. I am doing stuff in the fun() but here i am just giving my example. Here it the code:

```
// Helper function
string fun() {
string abc = "Daniweb";
// print here #1
return abc;
}
// ...
```

Hi group,

I'm discovering that my Excel spreadsheets that are being created by a VB.net app I've written isn't completely closing them as they should be. I'm struggling to understand why and how to fix this. Here is the code for the portion of the app that creates the workbook, ...