?

算法描述

　　如果连通图是一个网，则称该网中所有生成树中权值总和最小的生成树为最小生成树，也称最小代价生成树。利用Prim算法构造的最小生成树方法思想：

　　假设G=(V,E)是一个具有n个顶点的连通网，顶点集V={v1,v2,...,vn}.设所求的最小生成树T=(U,TE),其中U是T的顶点集，TE是T的边集，U和TE初值均为空集。

　　Prim算法的基本思想如下：首先从V中任取一个顶点(假定取v1),将生成树T置为仅有一个结点v1的树，即U={v1};然后只要U是V的真子集，就在所有那些一个端点在T中，另一个端点在T外的边中，找一条最短（即权值最小 )的边。假定符合条件的最短边为(vi,vj),则把该条边和其不在T中的顶点vj，分别并入T的边集TE和顶点集U。如此进行下去，每次往生成树里并入一个顶点和一条边，直到把所有顶点都包括进生成树T为止。此时，必有U=V，TE中有n-1条边，则T=(U,TE)是G的一棵最小生成树。

算法实现

　　设一个edge数组，记录从顶点Ｕ集到Ｖ－Ｕ的代价最小的边，每条边的信息包括边的始点和，终点和权值。从顶点u出发，利用prim算法求最小生成树步骤如下：

　　(1) 初始化edge数组，记录顶点u到图中其余结点的代价最小的n-1的边。

　　(2) 将顶点u加入Ｕ中。

　　(3) 当U不等于V时，做如下处理。

　　　　1) 从edge数组中选一条代价最小的边。

　　　　2) 将该边的终点加入U中。

　　　　3) 调整edges数组，使它始终记录顶点U到V-U的代价最小的边。

算法代码

?

// 定义边结构体
typedef struct{
	int start;
	int end;
	int cost;
}Edge;


/* 
 *Prim算法求最小生成树
 * */
void Prim_MG(MGraph MG,char vs){
	Edge edge[MAX_VEX_NUM];
	int i,j,k,v,min;
	int s = getIndexOfVexs(vs,&MG);
	//初始化边
	for(i = 1;i <= MG.vexnum;i++){
		if(s != i){
			edge[i].start = s;
			edge[i].end = i;
			edge[i].cost = MG.arcs[s][i];
		
		}
	}
	//首先将s加入生成树集合中
	edge[s].cost = 0;
	for(i = 2;i <= MG.vexnum;i++){
		min = 1000;
		for(j = 1;j<= MG.vexnum;j++){
			if(edge[j].cost != 0 && edge[j].cost < min ){
				min = edge[j].cost;
				k = j;
			}
		}
		v = edge[k].end;
		edge[v].cost = 0; // 加入新节点

		//输出生成树中的边
	 	printf(%c %c %d
,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]);

		//重新调整数组
		for(j = 1;j <= MG.vexnum;j++){
			if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){
				edge[j].start = k;
				edge[j].end = j;
				edge[j].cost = MG.arcs[v][j];
			}
		}
	}

}

?

算法说明

　　假设图中有n个顶点，则第一个进行初始化的循环语句的频度为n,第二个循环语句频度为n-1。其中有两个内循环；其一是在edge数组中找权值最小的边，其频度为n-1,其二是重新调整edge数组的边，频度为n,所以Prim算法的时间复杂度为O(n^2)，而与图中的边数无关，因此适用于求稠密的最小生成树。

?

完整代码

?

/*
 * =====================================================================================
 *
 *       Filename:  Prim.c
 *
 *    Description:  最小生成树算法之Prim算法 
 *
 *        Version:  1.0
 *        Created:  2015年03月11日 15时27分19秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  jesson20121020 (), 997287955@qq.com
 *   Organization:  
 *
 * =====================================================================================
 */

#include 
  
   
#include 
   
     #define MAX_VEX_NUM 50 #define UN_REACH 1000 typedef char VertexType; typedef enum { DG, UDG } GraphType; typedef struct { VertexType vexs[MAX_VEX_NUM]; int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; int vexnum, arcnum; GraphType type; } MGraph; /** * 根据名称得到指定顶点在顶点集合中的下标 * vex 顶点 * return 如果找到，则返回下标，否则，返回０ */ int getIndexOfVexs(char vex, MGraph *MG) { int i; for (i = 1; i <= MG->vexnum; i++) { if (MG->vexs[i] == vex) { return i; } } return 0; } /** * 创建邻接矩阵 */ void create_MG(MGraph *MG) { int i, j, k,weight; int v1, v2, type; char c1, c2; printf(Please input graph type DG(0) or UDG(1) :); scanf(%d, &type); if (type == 0) MG->type = DG; else if (type == 1) MG->type = UDG; else { printf(Please input correct graph type DG(0) or UDG(1)!); return; } printf(Please input vexmun : ); scanf(%d, &MG->vexnum); printf(Please input arcnum : ); scanf(%d, &MG->arcnum); getchar(); for (i = 1; i <= MG->vexnum; i++) { printf(Please input %dth vex(char):, i); scanf(%c, &MG->vexs[i]); getchar(); } //初始化邻接矩阵 for (i = 1; i <= MG->vexnum; i++) { for (j = 1; j <= MG->vexnum; j++) { if(i == j) MG->arcs[i][j] = 0; else MG->arcs[i][j] = UN_REACH; } } //输入边的信息，建立邻接矩阵 for (k = 1; k <= MG->arcnum; k++) { printf(Please input %dth arc v1(char) v2(char) weight(int): , k); scanf(%c %c %d, &c1, &c2,&weight); v1 = getIndexOfVexs(c1, MG); v2 = getIndexOfVexs(c2, MG); if (MG->type == 1) MG->arcs[v1][v2] = MG->arcs[v2][v1] = weight; else MG->arcs[v1][v2] = weight; getchar(); } } /** * 打印邻接矩阵和顶点信息 */ void print_MG(MGraph MG) { int i, j; if(MG.type == DG){ printf(Graph type: Direct graph ); } else{ printf(Graph type: Undirect graph ); } printf(Graph vertex number: %d ,MG.vexnum); printf(Graph arc number: %d ,MG.arcnum); printf(Vertex set: ); for (i = 1; i <= MG.vexnum; i++) printf(%c , MG.vexs[i]); printf( Adjacency Matrix: ); for (i = 1; i <= MG.vexnum; i++) { j = 1; for (; j < MG.vexnum; j++) { printf(%d , MG.arcs[i][j]); } printf(%d , MG.arcs[i][j]); } } // 定义边结构体 typedef struct{ int start; int end; int cost; }Edge; /* *Prim算法求最小生成树 * */ void Prim_MG(MGraph MG,char vs){ Edge edge[MAX_VEX_NUM]; int i,j,k,v,min; int s = getIndexOfVexs(vs,&MG); //初始化边 for(i = 1;i <= MG.vexnum;i++){ if(s != i){ edge[i].start = s; edge[i].end = i; edge[i].cost = MG.arcs[s][i]; } } //首先将s加入生成树集合中 edge[s].cost = 0; for(i = 2;i <= MG.vexnum;i++){ min = 1000; for(j = 1;j<= MG.vexnum;j++){ if(edge[j].cost != 0 && edge[j].cost < min ){ min = edge[j].cost; k = j; } } v = edge[k].end; edge[v].cost = 0; // 加入新节点 //输出生成树中的边 printf(%c %c %d ,MG.vexs[edge[v].start],MG.vexs[edge[v].end],MG.arcs[edge[v].start][edge[v].end]); //重新调整数组 for(j = 1;j <= MG.vexnum;j++){ if(edge[j].cost != 0 && MG.arcs[v][j] != 0 && MG.arcs[v][j] < edge[j].cost){ edge[j].start = k; edge[j].end = j; edge[j].cost = MG.arcs[v][j]; } } } } /** * 主函数 */ int main(void) { MGraph MG; char startVex; create_MG(&MG); print_MG(MG); printf( Please input the start vex(char):); scanf(%c,&startVex); printf( The result of Prim: ); Prim_MG(MG,startVex); return EXIT_SUCCESS; } 
   
  

?

?

运行演示

?

?