Prim算法原理是什么以及完整C代码的实现

今天就跟大家聊聊有关Prim算法原理是什么以及完整C代码的实现，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

创新互联致力于互联网网站建设与网站营销，提供成都网站设计、做网站、网站开发、seo优化、网站排名、互联网营销、成都小程序开发、公众号商城、等建站开发，创新互联网站建设策划专家，为不同类型的客户提供良好的互联网应用定制解决方案，帮助客户在新的全球化互联网环境中保持优势。

Prim算法

涉及到的几个基础知识

• 生成树： 一个连通图的生成树是它的极小连通子图，在n个顶点的情形下，有n-1条边。生成树是对连通图而言的，是连通图的极小连通子图，包含途中所有顶点，有且仅有n-1条边。非连通图的生成树则组成一个声称森林；若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。

• 图的遍历： 和树的遍历相似，若从图中某顶点出发，访问遍途中每个顶点，且每个顶点仅访问一次，此过程称为图的遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。图的常用遍历顺序有两种：深度优先搜索（DFS）和广度优先搜索（BFS），对每种搜索顺序，访问各顶点的顺序也不是唯一的。

• 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G'，称作图G的生成树。一个图可以有多个生成树，从不同的顶点除法，采用不同的遍历顺序，遍历时所经过的边也就不同。

• 最小生成树：在图论中，常常将树定义为一个无回路连通图。对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树成为图的最小生成树（MST）。

• MST性质：MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。

Prim算法

• 基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V）、TE＝{}开始。重复执行下列操作：

• 在所有u∈U，v∈V－U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止。
  此时，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

• Prim算法的核心:始终保持TE中的边集构成一棵生成树。

• Prim算法举例：

采用的是顶点数为6的无向连通图：

设集合V={A,B,C,D,E,F}，即所有顶点的集合。

集合U为最小生成树的结点。

按照Prim算法：

1. 将A加入U，此时，U={ A }，V-U={ B，C，D，E}；

2. 与A邻接的顶点有B，C，D。（A，B）、（A，C）、（A，D），权值分别为6、1、5，因而选定（A，C）为最小生成树的一条边；

3. 将上一步选定的在V-U中的顶点C加入U，此时，U={A，C}， V-U={ B，D，E，F}；

4. V-U中与U中顶点组成的边有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（C，F），权值分别为6、5、5、5、6、4，因而选定（C，F）为最小生成树的一条边；

5. 将F加入U中，此时U={ A，C，F} ， V-U={ B， D，E}；

6. V-U中与U中顶点组成的边有（A，B）、（A，D）、（C，B）、（C，D）、（C，E）、（F，D）、（F，E），权值分别为6、5、5、5、6、2、6，选定（F，D）为最小生成树的一条边；

7. 将D加入U中，此时，U={ A，C，F，D}， V-U={ B，E}；

8. V-U中与U中顶点组成的边有（A，B）、（C，B）、（C，E）、（F，E），权值分别为6、5、6、6，选定（C，B）为最小生成树的一条边。

9. 将B加入U中，此时U= {A，C，F ，D，B }, V -U={E };

10. V-U中与U中顶点组成的边有（B，E）、（C，E）、（F，E），权值分别为3、6、6，选定（B，E）为最小生成树的一条边。

11. 将E加入U中，此时U={A ，C，F，D，B，E}，完成MST的生成。

其生成过程图示如下：

1.  

         

2. 
   

3. 
   

4. 
   

5. 
              

Prim算法C代码

难点是prim函数中的两个辅助数组的具体含义：lowcost数组，顾名思义，最小代价。也就是 lowcost[k] 保存着V-U中编号为k的顶点到U中所有顶点的最小权值。closest数组，顾名思义，距离最近。 也就是 closest[k] 保存着U中到V-U中编号为K的顶点权值最小的顶点的编号。这两个数组的元素是随着顶点不断加入U集合而动态变化的。程序中采用邻接矩阵法创建图。

/* 求最小生成树的prim算法 */

#include 
#include 

#define MaxSize 20
#define MAX 10000

typedef char VertexType;

//定义图 的邻接矩阵表示法结构
typedef struct Graph {
	VertexType ver[MaxSize+1];
	int edg[MaxSize][MaxSize];
}Graph;

//邻接矩阵法图的生成函数
void CreateGraph( Graph *g )
{
	int i = 0;
	int j = 0;
	int VertexNum;
	VertexType Ver;

	printf("请输入图的顶点:\n");
	while( '\n' != (Ver=getchar()) )
		g->ver[i++] = Ver;
	g->ver[i] = '\0';

	VertexNum = strlen(g->ver);
	printf("请输入相应的的邻接矩阵:\n");
	for( i=0; iedg[i][j]);
}

//打印图的结点标识符和邻接矩阵
void PrintGraph( Graph g )
{
	int i, j;
	int VertexNum = strlen(g.ver);
	printf("图的顶点为:\n");
	for( i=0; iedg[i][j] )
				g->edg[i][j] = MAX;
}

//运用prim算法求最小生成树
void prim( Graph g, int VerNum, int *parent )
{
	int i, j, k;
	int lowcost[MaxSize];
	int closest[MaxSize], used[MaxSize];
	int min;

	for( i=0; i

测试结果：数据即为前面所讲的图。

看完上述内容，你们对Prim算法原理是什么以及完整C代码的实现有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。

本文标题：Prim算法原理是什么以及完整C代码的实现
分享链接：http://shouzuofang.com/article/jossio.html