Kruskal算法求最小生成树

Kruskal算法简单实现如下：

void Kruskal(V,T){
	T=V;						//初始化树T,仅含顶点
	numS=n;						//连通分量数
	while(numS>1){				//连通分量数>1
		//从E中取出权值最小的边(v,u)
		if(v和u属于不同连通分量){
			T=T∪{(u,v)};		//将边加入树中
			numS--;				//连通分量数--
		}
	}	
}

kruskal算法实现过程：

具体实现：

//储存各条边的信息
struct ed{
	int Head;			//头结点
	int Tail;			//尾节点
	int lowcost;		//权值
}Edge[MVNum];

//邻接矩阵
typedef struct{
	//int vex[MVNum];
	int arc[MVNum][MVNum];
	int vexnum, arcnum;
}AMGraph;

int LocateVex(AMGraph *G,VerTexType v){
	for(int i=0;i<G->vexnum;i++){
		if(G->vex[i]==v)
			return i;
	}
	return -1;
}
 
int CreateGraph()
{
	MGraph* G;
 	G->vexnum=x;
    G->arcnum=x;
	//初始化为无穷
    for(i=0;i<G->vexnum;i++){
        for(j=0;j<G->vexnum;j++)
            G->arc[i][j]=MAX;
    }  
    //将边和权值写到邻接矩阵中，连通即为权值，否则为无穷大，同时记录边信息
	for(k=0;k<G->arcnum;k++){	
		Edge[k].Head=v1;
		Edge[k].Tail=v2;
		Edge[k].lowcost=w;
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		G->arc[i][j]=weight;	
	}
}

Kruskal算法：

//将边按权值升序排序
void Sort(AMGraph *G){	
	for(i=0;i<G->arcnum-1;i++){
		min=i;
		for(j=i+1;j<G->arcnum;j++)
			if(Egde[min].lowcost>Edge[j].lowcost)
				min=j;					
		if(min!=i)		
			swap(Edge[i],Edge[min]);				
	}
}

void Kruskal(AMGraph *G)
{
	Sort(G);
	//记录结点i所在的连通分量，初始化为自己
	int Vexset[G->vexnum];	
	for(i=0;i<G->vexnum;i++)
		Vexset[i]=i;
	//按权值从小到大遍历所有边
	for(i=0;i<G->arcnum;i++){
		v1=Edge[i].Head;
		v2=Edge[i].Tail;
		vs1=Vexset[v1];
		vs2=Vexset[v2];
		//若头尾两个结点不在一个连通分量
		if(vs1!=vs2)			
			//找到边(v1,v2)
			//统一连通分量，即将vexset所有vs2置成vs1.如vs1=1,vs2=3：[1,1,3,3,5,6]->[1,1,1,1,5,6]			
			for(j=0;j<G->vexnum;j++)
				if(Vexset[j]==vs2)
					Vexset[j]=vs1;		
	}
}

Kruskal还是比Prim容易理解的;