1,105,225 Community Members

C++ code for Kruskal Algorithm

Member Avatar
ravi_forum
Newbie Poster
4 posts since Aug 2006
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
2
 

Sir,

I wanted to know the implementation code for krushkal algorithm in C++.

Anyone can help me to give the code.
ThnQ

Member Avatar
Grunt
Junior Poster
147 posts since Jul 2006
Reputation Points: 19 [?]
Q&As Helped to Solve: 12 [?]
Skill Endorsements: 0 [?]
 
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

Member Avatar
andor
Posting Whiz in Training
273 posts since Jun 2005
Reputation Points: 25 [?]
Q&As Helped to Solve: 29 [?]
Skill Endorsements: 0 [?]
 
1
 

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

Member Avatar
~s.o.s~
Failure as a human
10,399 posts since Jun 2006
Reputation Points: 2,496 [?]
Q&As Helped to Solve: 992 [?]
Skill Endorsements: 72 [?]
Administrator
Featured
 
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.

Member Avatar
smart_pallav
Newbie Poster
1 post since Oct 2007
Reputation Points: -2 [?]
Q&As Helped to Solve: 1 [?]
Skill Endorsements: 0 [?]
 
-1
 

C++ code for kruskal algorithm...
will you provide me..

Question Answered as of 6 Years Ago by smart_pallav, andor, ~s.o.s~ and 1 other
Member Avatar
zandiago
Nearly a Posting Maven
2,463 posts since Jun 2007
Reputation Points: 115 [?]
Q&As Helped to Solve: 55 [?]
Skill Endorsements: 0 [?]
Featured
 
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!

Member Avatar
rachnaa
Newbie Poster
1 post since Mar 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

plz mail me d java codes for prim's , kruskal's nd single source shortest path algorithms.
my id is << email id snipped >>

Member Avatar
er.chiraggupta
Newbie Poster
2 posts since Jan 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
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

Member Avatar
happyuk
Newbie Poster
3 posts since Sep 2008
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

I know of two links you may be interested in.

  1. An ordinary C++ implementation of Kruskal's algorithm
  2. 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
Member Avatar
naamurad
Newbie Poster
3 posts since Oct 2013
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
-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

You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article