图的最小生成树求法汇总

普里姆算法
从连通图N=(U,E)中招最小生成树T=(U,TE).
1.算法思想
<1>若从顶点v0出发构造,U={v0},TE={};
<2>先找权值最小的边(u,v),其中u∈U且v∈V-U,并且子图不构成环,则
U=U∪{v},TE=TE∪{(u,v)};

<3>重复(2),直到U=V为止.则TE中必有n-1条边,T=(U,TE)就是最小生成树

2.
设用邻接 矩阵 ((二维数组))表示图，两个顶点之间不存在边的权值为机内允许的最大值。
为便于算法实现，设置一个一 维数组
closedge[n]，用来保存，V-U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是

struct 
{
	int adjvex;/*边所依附于U中的顶点*/
	int lowcost;/*该边的权值*/
}closedge[MAX_EDGE];

在Prime算法中，图采用邻接矩阵存储，所构造的最小生成树用一维数组存储其n-1条边，
每条边的存储结构描述：

typedef struct MSTEdge
{
	int vex1,vex2;/*边所依附的图的两个顶点*/
	WeightType weight;/*边的权值*/
	
}MSTEdge;

算法实现
#define INFINITY MAX_VAL
MSTEdge *Prim_MST(AdjGraph *G,int u)
{
	MSTEdge TE[];
	int j,k,v,min;
	for(j=0;j<G->vexnum;j++)
	{
		closedge[j].adjvex=u;
		closedge[j].lowcost=G->adj[j][u];
	}/*初始化数组closedge[n]*/
	
	closedge[u].lowcost=0;
	TE=(MSTEdge*)malloc((G->vexnum-1)*sizeof(MSTEdge));
	
	for(j=0;j<G->vexnum;j++)
	{
		min=INFINITY;
		for(v=0;v<G->vexnum;v++)
		 if(closedge[v].lowcost!=0&&closedge[v].lowcost<min)
		 {min=closedge[v].lowcost;k=v;}
		TE[j].vex1=closedge[k].adjvex;
		TE[j].vex2=k;
		TE[j].weight=closedge[k].lowcost;
		closedge[k].lowcost=0;/*将顶点k并入U*/
		for(v=0;v<G->vexnum;v++)
		 if(G->adj[v][k]<closedge[v].lowcost)
		 {
			closedge[v].lowcost=G->adj[v][k];
			closedge[v].adjvex=k;
		 }/*修改数组closedge[n]的各个元素的值*
		 /
	}
	return (TE);
}/*求最小生成树的Prim算法*/

克鲁斯卡尔(Kruskal)算法
1 算法思想
设G=(V, E)是具有n个顶点的连通网,T=(U, TE)是其最小生成树。初值：U=V，，TE={} 。
对G中的边按权值大小从小到大依次选取。
<1>选取权值最小的边(vi，vj)，若边(vi,vj)加入到TE后形成回路，则舍弃该边(vi，vj) ；
否则，将该边并入到TE中，，即TE=TE∪{(vi,vj)} 。

<2>重<1>，直到TETE中包含有n-1条边为止。

2 算法实现说明
Kruskal 算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路??
简单的解决方法是：定义一个一维数组Vset[n] ，存放图T中每个顶点所在的连通分量的编号。
◆初值：Vset[i]=i，表示每个顶点各自组成一个，连通分量，连通分量的编号简单地使用顶点在图中的位置((编号))。
◆当往T中增加一条边(vi，vj) 时，先检查Vset[i]和Vset[j]值：
☆若Vset[i]=Vset[j]：表明 ：vi和vj处在同一个连通分量中，，加入此边会形成回路
☆ 若Vset[i]≠Vset[j]，则 加入此边不会形成
回路 ，将此边加入到生成树的边集中。
◆ 加入一条新边后，将两个不同的连通分量合并
将一个 连通分量的编号换成另 一个 连通分量的编
号。
算法实现

MSTEdge *Kruskal(ELGraph *G)
{
	MSTEdge TE[];
	int j,k,s1,s2,Vset[];
	WeightType w;
	Vset=(int*)malloc(G->vexnum*sizeof(int));
	for(j=0;j<G->vexnum;j++)
		Vset[j]=j;/*初始化数组Vset[n]*/
	sort(G->edgelist);/*对表按权值从小到大排序*/
	j=0;k=0;
	while(k<G->vexnum-1&&j<G->edgenum)
	{
		s1=Vset[G->edgelist[j].vex1];
		s2=Vset[G->edgelist[j].vex2];
		/*若边的两个顶点的连通分量编号不同,边加入到TE中*/
		if(s1!=s2)
		{
			TE[k].vex1=G->edgelist[j].vex1;
			TE[k].vex2=G->edgelist[j].vex2;
			TE[k].weight=G->edgelist[j].weight;
			k++;
			for(v=0;v<G->vexnum;v++)
				if(Vset[v]==s2)Vset[v]=s1;
				
		}
		j++;
	}
		free(Vset);
		return (TE);
}