欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构(C实现)------- 最小生成树之Prim算法

程序员文章站 2022-03-23 20:08:09
  算法描述   如果连通图是一个网,则称该网中所有生成树中权值总和最小的生成树为最小生成树,也称最小代价生成树。利用Prim算法构造的最小生成树方法思想:   假...

 

算法描述

  如果连通图是一个网,则称该网中所有生成树中权值总和最小的生成树为最小生成树,也称最小代价生成树。利用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集到V-U的代价最小的边,每条边的信息包括边的始点和,终点和权值。从顶点u出发,利用prim算法求最小生成树步骤如下:

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

  (2) 将顶点u加入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 如果找到,则返回下标,否则,返回0
 */
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;
}

 

 

运行演示

 

 

jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ gcc -o Prim Prim.c
jesson@jesson-HP:~/develop/workspace/c_learning/csdn/Prim$ ./Prim 
Please input graph type DG(0) or UDG(1) :1
Please input vexmun : 4
Please input arcnum : 5
Please input 1th vex(char):a
Please input 2th vex(char):b
Please input 3th vex(char):c
Please input 4th vex(char):d
Please input 1th arc v1(char) v2(char) weight(int): a b 1
Please input 2th arc v1(char) v2(char) weight(int): a c 3
Please input 3th arc v1(char) v2(char) weight(int): a d 4
Please input 4th arc v1(char) v2(char) weight(int): b c 2
Please input 5th arc v1(char) v2(char) weight(int): c d 3

Please input the start vex(char):a

The result of Prim:
a b 1
b c 2
c d 3