克鲁斯卡尔算法建立最小生成树

克鲁斯卡尔算法，是每次选出权值最小的边构成最小生成树，选出边时，要避免形成环。最终选出结点数减一条边即可。（避免形成环的问题，采用标号法（并查集），一开始，每个结各自为一个集合，分别给出各自不同大小的标号，选出的边的两端结点的标号将大的那个改成小的，以后选出的边的端点标号不能相同。）

#include
#define N 100
int sum=0;//权值和 
using namespace std;
//边节点 
typedef struct vexnode {
	int adjvex;
	char v;
	struct  vexnode *nextarc;
	float info;
}ArNode;
typedef struct Vnode{  //顶点信息 
	char data;
	ArNode *firstarc; //指向第一个边结点 
}Vonde,Adjust[100]; 
typedef struct {
	Adjust survice;//邻接表 
	int vexnum,acrnum;//图的当前顶点数和边数 
}ALgraph;

//邻接表查找
 int locate1(ALgraph&R, char v,int n){//找出字符为v的下标 
 	int j,i;
 	for(i=1;i<=n;i++){
 		if(R.survice[i].data==v){
 			j=i;
		 }
	 }
	 return j;
 } 
void creatUND(ALgraph &R){
	char v1,v2;//顶点的数据值 
	int i1,i2;//输入的两个顶点的位置和权值 
	float i3;//权值 
	printf("请输入顶点数和边数："); 
	cin>>R.vexnum>>R.acrnum; //输入顶点数和边数 
	printf("请输入各个顶点的值：n"); 
	for(int i=1;i<=R.vexnum;i++){
		cin>>R.survice[i].data;//输入各个顶点的信息 
		R.survice[i].firstarc=NULL;
		 
	}
   
    printf("请输入每条边依附的两个结点和权值：n");
	for(int i=1;i<=R.acrnum;i++){
		cin>>v1>>v2>>i3;
		i1=locate1(R,v1,R.vexnum);
		i2=locate1(R,v2,R.vexnum);
		ArNode *p=new ArNode;
		p->info=i3; //记录权值 
		p->v=v1;//记录边点的值 
		p->adjvex=i2;// 记录顶点的值 
		p->nextarc=R.survice[i2].firstarc; //利用头插法把第i1个的顶点插入到第i2个邻接表中 
		R.survice[i2].firstarc=p;//建立的邻接表表示的图为有向图，所以只记录一边，所以下面的部分代码给注释掉了 
	
	} 
	     
}
//协助结构体，用来记录边的起始点，终点，权值信息 
typedef struct end{
	 char start;//边的起点 
	 char end;//变得终点 
	 int  w;//边的权值 
}Edge[100]; 
  
//将边按照权值大小进行排序 
void sort(Edge &E,ALgraph &R){
	char b;
	int num;
	 int m=R.acrnum;
	 for(int i=0;ij){
	  	return i;
	}else 
	return j;
} 
//找出两结点的标号的小的那个
int min (int i,int j){
	if(iv;
	   		E[u].w=p1->info;
	   		u++;
	   		p1=p1->nextarc;
		   }
	   }
	   sort(E,G); //将每条边按照权值的大小排序
	   int n=0;//要挑选出边的下标 
	   for(int i=0;i<=G.vexnum-1;i++){//边的结构体下标是从零开始的 
	   	char head1 =E[n].start;//记录选出边的起始点 
	   	char end1 =E[n].end;//记录选出边的终点 
	   	if(parent[locate1(G,head1,G.vexnum)]!=parent[locate1(G,end1,G.vexnum)]){// 如果结点的标号不相等的话，将权值加上 
	   		  sum+=E[n].w; 
		  int  maxv=max(parent[locate1(G,head1,G.vexnum)],parent[locate1(G,end1,G.vexnum)]);//得到边两端结点标号的最大值 
		  int  minv=min(parent[locate1(G,head1,G.vexnum)],parent[locate1(G,end1,G.vexnum)]);//得到边两端结点标号的最小值 
		     parent[locate1(G,head1,G.vexnum)]=minv;  
			 parent[locate1(G,end1,G.vexnum)]=minv;//他俩选出后成为一个集合，将标号都改为最小值 
		
			 for (int j=1;j<=G.vexnum;j++){//将结点中所有标号都为边两端标号最大值的结点标号都改为最小值 
			 	if(parent[j]==maxv){
			 		  parent[j]=minv;
				 }
			 }
			
		 printf("<%c ,%c> n",head1,end1); //输出找出变的两个结点 
		
	}
		 n++;
	   } 
	   printf("最小权值之和为：%d",sum); 
	   
	
}
int main (){
	ALgraph R;
	Edge E;//有关边的结构体 
	creatUND(R);
	minspantree_Kruskal(R,E);
	return 0;
}