【算法导论】最小生成树（prim算法）

一，定义：

没有权值时：一个有n个节点的联通图，生成树是，极小联通子图。包含图中所有节点，且有保持图联通的最少的边。

边有权值时：无向联通图G=(V,E)，权值函数，w:E->R。找到G的一棵最小生成树，使得 w(T)最小。w(T)为最小生成树所有边权值和。

二，prime算法

1:初始化:U={u 0},TE={f}。 节点集U=0，边集TE=NULL，

　 2:在所有u∈U, v∈V－U的边 (u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。

　 3:如果U=V,则算法结束;否则重复步骤2。

说明：步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。

三，源码

#include"stdio.h"
#include"malloc.h"
#define MaxSize 10
#define MaxNumber  999999
/*prim就是用 邻接矩阵存储的*/
/*这里是无向图*/
typedef struct MGraph//
{
	char vertex[MaxSize];
	int arc[MaxSize][MaxSize];
	int vertexNum,arcNum;//顶点数 边数 
}MGraph,*M; 
                  //顶点     顶点数  边数 
void CreateMGraph(MGraph *G,char ver[],int n,int e)//创建树 
{
	G->vertexNum=n;
	G->arcNum=e;
	int i,j;
	int ver1,ver2;	
	
	for(i=0;i<G->vertexNum;i++)
	    {
    		G->vertex[i]=ver[i]; 
   		    //printf("%5c\n",G.vertex[i]);
    	} 
		 	     
    for(i=0;i<G->vertexNum;i++)
       for(j=0;j<G->vertexNum;j++)
           G->arc[i][j]=MaxNumber;//初始化数组 以后有边的 赋值
           
	for(i=0;i<G->arcNum;i++)
	 {/*注意输入时 不要超过数组的下标 从0开始*/
	 	printf("please input the edge of two vertex\n");
	 	scanf("%d%d",&ver1,&ver2);
 		G->arc[ver1][ver2]=1;
 		G->arc[ver2][ver1]=1;
 	 }	
 	 //printf("%d\n",G.vertexNum);
}
void outPut(MGraph *G)
{   int i,j;

  //printf("%d",G->vertexNum);
	
	for(i=0;i<G->vertexNum;i++)
	   printf("%8c",G->vertex[i]);
    
    printf("\n");
    
	for(i=0;i<G->vertexNum;i++)
	{
		for(j=0;j<G->vertexNum;j++)
	    {
    		printf("%8d",G->arc[i][j]);
    	} 
		printf("\n");
	}  
	
} 
int MinEdge(int lowcost[],int n)//如果 不可达的边赋值为0  肯定出错 应该赋值为无穷 MaxNumber 
                                //这里要返回的是下标 而不是最小值 
{
	int i=0;
	while(lowcost[i]==0)
	     ++i;
	int min=lowcost[i];
	int min_n=i;
	
	for(int j=i;j<n;j++)
	   if(lowcost[j]!=0&&lowcost[j]<min) 
	         {
         		min=lowcost[j];
         		min_n=j;
         	} 
    //printf("sssssss%d\n",min);
    return min_n;
    //return min;
}
void prim(MGraph *G)
{
	int i,j,k;
	int lowcost[G->vertexNum];//lowcost[k]记录顶点 k 到已经加入最小生成子树 的权值
	int adjvex[G->vertexNum]; 
	 //printf("%d\n",G->vertexNum);
	for(i=1;i<G->vertexNum;++i)//这里 i 是从 1开始 
	{
		lowcost[i]=G->arc[0][i];  //初始化 U中只有 0这个顶点 让 lowcost 数组存放 0到各个顶点权值 
                                  //其实  lowcost 数组 存放没有并入 U 中的点  到U 中最小权值，adjvex 则对应 该顶点 
		adjvex[i]=0; //顶点 i 到 U中边中最小权值的 顶点 
	}
	lowcost[0]=0;
	
	for(i=1;i<G->vertexNum;++i)
	{
		k=MinEdge(lowcost,G->vertexNum);//在lowcost[]数组中寻找最短的边
		printf("<%d,%d>--$:%d\n",k,adjvex[k],lowcost[k]); //输出加入到 U 中的边 
		lowcost[k]=0;  //将顶点k 加入集合U
		
		for(j=1;j<G->vertexNum;++j)
		{
			if(G->arc[k][j]<lowcost[j])
			{
				lowcost[j]=G->arc[k][j];
				adjvex[j]=k;
			}
		} 
		 
	}
}
/*思考过程： 0 先在U 内 lowcost 为 V-U  内点到 0 cost
             选中到 0 cost最小的 k,并通过lowcost[k]=0使得k加入 U,比较V-U 到0  跟到 k cost 取小放入 lowcost
			 再选l 使得 V-U  中到 U 中最小边  ,l加入U， 让 V-U中其余点到(U-l)cost 跟 到 l cost 比较  取小的放入 lowcost
			 
			 综上，lowcost 存放的是 V-U 的所有点 到 U的 最小权值。其中 lowcost=0表示加入U 查找最小值时，不再搜索 
			 求最小生成树，就是寻找分割的两部分之间的 最小权值的边。 
 */
int main()
{
	MGraph *graph=(MGraph*)malloc(sizeof(MGraph));
	
	
	char ver[4]={'a','b','c'};
	int n=3;//顶点数
	int e=2; 
	
	//graph->vertexNum=n;//这个必须加上 
   // printf("%d\n",graph->vertexNum);
		 
	CreateMGraph(graph,ver,n,e); 
	
   // printf("%d\n",graph->vertexNum);
	
	outPut(graph);
	prim(graph);
	
}