kruskal.cpp

kruskal( 利用堆

 #include<stdlib.h> 
#include<stdio.h> 
#include<iostream> 
#include<string.h> 
using namespace std; 




typedef struct ebox{ 
int mark; 
int ivex,jvex,weight; 
    struct  ebox *ilink,*jlink; 
}ebox; 
typedef struct vexbox{ 
int data; 
int mark; 
ebox * firstedge; 
}vexbox; 
typedef struct{ 
vexbox adjmulist[20]; 
int vexnum,edgnum; 
}amlgraph; 
typedef struct{ 
ebox *edgs; 
int length; 
int listsize; 
}sqlist;//用于进行堆排序 

void heapsort(sqlist &L); 

void initsql( sqlist &L ) 
{ 
L.edgs=new ebox[20]; 
L.length=0; 
L.listsize=20; 
} 
void creataml(amlgraph &G,sqlist &L) 
{ 
freopen("kruskal2.txt","r",stdin); 
int i,j,k,v1,v2,w; 
cin>>G.vexnum>>G.edgnum; 

L.length=G.edgnum; 

for(i=0;i<G.vexnum;i++) 
{ 
cin>>G.adjmulist[i].data; 
G.adjmulist[i].firstedge=NULL; 
G.adjmulist[i].mark=0; 
} 

for(k=0;k<G.edgnum;k++) 
{ 
cin>>v1>>v2>>w; 
i=v1-1; j=v2-1; 
ebox edg={0,i,j,w,NULL,NULL}; 
L.edgs[k] = edg; 
} 

heapsort(L); 

ebox *p; 
for(k=0;k<G.edgnum;k++) 
{ 
if(G.adjmulist[ L.edgs[k].ivex ].firstedge == NULL) G.adjmulist[ L.edgs[k].ivex ].firstedge = &L.edgs[k]; 
else   
{ 
p = G.adjmulist[ L.edgs[k].ivex ].firstedge; 
while( p->ilink ) 
{p=p->ilink;} 
p->ilink = &L.edgs[k] ; 
} 
} 
for(k=0;k<G.edgnum;k++) 
{ 
if(G.adjmulist[ L.edgs[k].jvex ].firstedge == NULL) G.adjmulist[ L.edgs[k].jvex ].firstedge = &L.edgs[k]; 
else   
{ 
p = G.adjmulist[ L.edgs[k].jvex ].firstedge; 
while( p->jlink ) 
{p=p->jlink;} 
p->jlink = &L.edgs[k] ; 
} 
} 
} 

void heapadjust(sqlist &L,int s,int m) 
{ 
int rc,j; ebox rm; 
rc=L.edgs[s].weight; rm=L.edgs[s]; 
for( j=2*s;j<=m;j*=2 ) 
{ 
if( j<m && L.edgs[j].weight<L.edgs[j+1].weight ) ++j; 
if( rc >= L.edgs[j].weight ) break; 
L.edgs[s]=L.edgs[j]; s=j; 
} 
L.edgs[s]=rm; 
} 
void heapsort(sqlist &L) 
{ 
int i; ebox temp; 
for( i=L.length/2-1; i>=0; i-- ) 
{ 
heapadjust( L,i,L.length-1 ); 
} 
for( i=L.length-1; i>=1; i-- ) 
{ 
temp=L.edgs[0]; 
L.edgs[0]=L.edgs[i]; 
L.edgs[i]=temp; 
heapadjust( L,0,i-1 ); 
} 
} 

typedef struct{ 
int data; 
int parent; 
}ptnode; 
typedef struct{ 
ptnode nodes[100]; 
int r,n; 
}ptree; 
typedef ptree mfset; 

int find_mfset(mfset s,int i) 
{ 
if(i<0 || i>s.n) return -1; 
for(int j=i; s.nodes[j].parent >= 0; j=s.nodes[j].parent); 
return j; 
} 

/*void merge_mfset( mfset &s, int i, int j ) 
{ 
if(i<1 || i>s.n || j<1|| j>s.n )cout<<"error!"; 
s.nodes[i].parent=j; 
}*/ 
void mix_mfset( mfset &s,int i,int j ) 
{ 
if(i<0 || i>s.n || j<0 || j>s.n )cout<<"error!"; 
if( s.nodes[i].parent > s.nodes[j].parent ) 
{ 
s.nodes[j].parent+=s.nodes[i].parent;//根结点存放所含成员个数的负值。 
s.nodes[i].parent=j;  
} 
else 
{ 
s.nodes[i].parent += s.nodes[j].parent; 
s.nodes[j].parent=i; 
} 
} 

int fix_mfset(mfset &s,int i) 
{ 
int t;int j=0; 
if( i<0 || i>s.n )return -1; 
for( j=i;s.nodes[j].parent>0;j=s.nodes[j].parent ); 
for( int k=i;k!=j;k=t ) 
{ 
t = s.nodes[k].parent;  s.nodes[k].parent = j; 
} 
return j; 
} 

void kruskal(sqlist  &L,amlgraph G) 
{ 
mfset s; 
s.n=L.length; 
for( int i=0;i<L.length;i++ ) 
s.nodes[i].parent=-1; 

int temp1,temp2;   
// mix_mfset( s, L.edgs[0].ivex, L.edgs[0].jvex ); 

for( i=0;i<L.length;i++ ) 
{ 
temp1=find_mfset( s, L.edgs[i].ivex ) ; 
fix_mfset( s, L.edgs[i].ivex );//实现路径压缩 

temp2=find_mfset( s, L.edgs[i].jvex ) ; 
fix_mfset( s, L.edgs[i].jvex );//实现路径压缩 

if( temp1!=temp2 )// || (temp1==temp2 && temp1==0) 
{ 
mix_mfset( s, temp1, temp2 ); 
L.edgs[i].mark=1; 
 } 
else continue; 
} 
cout<<"the edg of the kruskal is:"<<endl; 
for( i=0;i<L.length;i++ ) 
{ 
cout<<i+1<<":"<<L.edgs[i].ivex+1<<"--"<<L.edgs[i].jvex+1<<"~"<<L.edgs[i].weight<<"  "; 
} 
cout<<endl; 
for( i=0;i<L.length;i++ ) 
{ 
if(L.edgs[i].mark==1)cout<<i+1<<":"<<L.edgs[i].ivex+1<<"--"<<L.edgs[i].jvex+1<<" "; 
} 
cout<<endl; 
} 

void main() 
{ 
amlgraph G; 
sqlist L; 
initsql(L); 
creataml(G,L); 
kruskal(L,G); 
}