Algoritmo de krushkal em c++

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (427 palavras )
  • Download(s) : 0
  • Publicado : 26 de novembro de 2011
Ler documento completo
Amostra do texto
/*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 asfollows
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 ismax nodes
#define M 10000 // M is max edges
#include
#include
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;isize;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->costcost)
return -1;
else if...
tracking img