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

男娘i 2022-03-30 11:42 232阅读 0赞

> \[本文是自己学习所做笔记。欢迎转载。但请注明出处：[http://blog.csdn.net/jesson20121020\]][http_blog.csdn.net_jesson20121020]

### 算法描写叙述 ###

假设连通图是一个网，则称该网中全部生成树中权值总和最小的生成树为最小生成树，也称最小代价生成树。利用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\n",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 <stdio.h>
    #include <stdlib.h>
    #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\n");
    	}
    	else{
    		printf("Graph type: Undirect graph\n");
    	}
    
    	printf("Graph vertex number: %d\n",MG.vexnum);
    	printf("Graph arc number: %d\n",MG.arcnum);
    
    	printf("Vertex set:\n ");
    	for (i = 1; i <= MG.vexnum; i++)
    		printf("%c\t", MG.vexs[i]);
    	printf("\nAdjacency Matrix:\n");
    
    	for (i = 1; i <= MG.vexnum; i++) {
    		j = 1;
    		for (; j < MG.vexnum; j++) {
    			printf("%d\t", MG.arcs[i][j]);
    		}
    		printf("%d\n", 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\n",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("\nPlease input the start vex(char):");
    	scanf("%c",&startVex);
    	printf("\nThe result of Prim:\n");
    	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

[http_blog.csdn.net_jesson20121020]: http://blog.csdn.net/jesson20121020