克鲁斯卡尔算法思想.cpp

按克鲁斯卡尔（Kruskal）算法思想

#include<iostream.h>
struct v
{int data;
v *next;
v *parent;
int use;
};
struct edge
{v init;
v end;
int weight;
int use;//如果为0没有用过或是没有作废；如果为1就是用过或是作废的边。
};
void storepicture(edge *(&a),int n,v *b,int m)
{cout<<"输入结点："<<endl;
for(int j=0;j<m;j++){cout<<"输入第"<<j+1<<"个顶点"<<endl;cin>>b[j].data;b[j].next=NULL;b[j].parent=NULL;}
cout<<"请由大到小输入每一条边:"<<endl;
for (int i=0;i<n;i++) { cout<<"输入第"<<i+1<<"条边"<<endl;
cout<<"输入起点："<<endl;
cin>>a[i].init.data;
cout<<"输入终点："<<endl;
cin>>a[i].end.data;
cout<<"输入权值："<<endl;
cin>>a[i].weight;
a[i].use=0;
}}
void searchandjoin(edge *(&a1),int k)//a1是图边集头指针，a2是最小生成树边集的头指针，k为所要删的边
//i2为最小生成树边集边数，j1图顶点数，j2为最小生成树的顶点数；
{

v *pt;
v p=a1[k].init;
for(;(p.parent==NULL)||(p.data==(a1[k].end.data));p=*(p.parent)) ; 
if(p.data==(a1[k].end.data)) ;
else {
	for(p=a1[k].init;p.next==NULL||p.data==a1[k].end.data;p=*(p.next)) ; 
	if(p.data==a1[k].end.data) ;
	else
	{pt=a1[k].init.next; 
     a1[k].init.use=1;
	 a1[k].end.use=1;
	a1[k].init.next=&(a1[k].end);
	a1[k].end.next=pt;
     cout<<"("<<a1[k].init.data<<","<<a1[k].end.data<<")"<<endl;
	}
	
}
a1[k].use=1;
}
void bubble(edge *(&a),int size)
{int i,work;
edge temp;
for(int pass=1;pass<size;pass++)
{work=1;
for (i=0;i<size-pass;i++)
if(a[i].weight<a[i+1].weight)
{temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
work=0;
}
if(work) break;
}
}
int seekedge(edge *(&a),int n)
{edge pt=a[n-1];
int k=n-1;
	for(;pt.use!=0||k<0;pt=a[k]) k--;
if(k!=0)	return k;
else 
return 0;
}
void main()
{int n,m;
cout<<"请输入图的边数："<<endl;
cin>>n;
cout<<"请输入图的顶点数："<<endl;
cin>>m;	
edge *pp=new edge[n];
v *dd=new v[m];	
storepicture(pp,n,dd,m);
bubble(pp,n);
int ff=n-1;
while (ff!=0)
{
searchandjoin(pp,ff);
ff=seekedge(pp,n);
}
v *pt;
if(pp[0].end.use!=1&&pp[0].init.use==1)
	{pt=pp[0].init.next;
	pp[0].end.use=1;
	pp[0].init.next=&(pp[0].end);
	pp[0].end.next=pt;
     cout<<"("<<pp[0].init.data<<","<<pp[0].end.data<<")"<<endl;
	}
if(pp[0].init.use!=1&&pp[0].end.use==1)
{pt=pp[0].end.next;
	pp[0].init.use=1;
	pp[0].end.next=&(pp[0].end);
	pp[0].init.next=pt;
     cout<<"("<<pp[0].init.data<<","<<pp[0].end.data<<")"<<endl;
	
	}
else cout<<"最小生成树已建成"<<endl;
}