prim算法

prim算法(普利姆算法)：对图G(V,E)设置集合S，存放已访问的顶点，然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点(记为u)，访问并加入集合S。之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。执行n次(n为顶点个数)，直到集合S已包含所有顶点。

算法实例演示

首先让我们来看一个example。如下图所示，图a是一个连通图（右图是图a对应的邻接矩阵，假设图中的边的权值大于0），我们现在基于该图来演示Prim算法的过程。


我们选择一个起点，然后在与起点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。假设起点是0节点，与0节点相连且未被选的节点是{1,2,3}，分别对应的权值是{6,1,5}，可见当前最小的权值1，权值最小的节点就是2节点，所以将2节点和0-2的边添加入生成树，如图b所示。

接着我们在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。当前已选节点是0,2节点，与已选节点相连且未被选的节点有{1,3,4,5}，分别对应的权值是{（6,5），（5,5），6,4,}，可见当前最小的权值4，权值最小的节点就是5节点，所以将5节点和2-5的边添加入生成树，如图c所示。（其实在编程时，我们只需记录与更新当前较小的那个权值，如与{1,3,4,5}对应的权值我们只需记录{5,5,6,4}，当然我们也需利用了另一个数组来加以区别当前权值对应的连接点，如当前权值{5,5,6,4}所对应的连接点就是{2,0,2,2}）

接着我们继续在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。当前已选节点是0,2,5节点，与已选节点相连且未被选的节点有{1,3,4}，分别对应的权值是{（6,5），（2,5,5），（6,6）,}（其实当前我们可只记录{5,2,6}，同时记录其对应的连接点分别是{2,5,2}），可见当前最小的权值2，权值最小的节点就是3节点，所以将3节点和5-3的边添加入生成树，如图d所示。

接着我们依照上一次的步骤继续在与已选节点相连且未被选的节点中选择一个权值最小的节点，将该节点与其相连边添加入生成树。如图e，f所示。最终图f就是我们通过Prim算法得到的最小生成树了。

prim算法基本思想：对图G(V,E)设置集合S来存放已被访问的顶点，然后执行n次下面的两个步骤(n为顶点个数)

1. 每次从集合V-S中选择与集合S最近的一个顶点(记为u)，访问u并将其加入集合S，同时把这条离集合S最近的边加入最小生成树。
2. 令顶点u作为集合S与集合V-S连接的接口，优化从u能到达的未访问顶点v与集合S的最短距离

prim算法的具体实现

1. 集合S的实现方法：使用一个bool型数组vis[]表示顶点是否已被访问。其中vis[i]==true表示顶点V_i已被访问，vis[i]==false则表示顶点V_i未被访问。
2. 不妨令int型数组d[]来存放顶点V_i(0<=i<=n-1)与集合S的最短距离。初始时除了起点s的d[s]赋为0，其余顶点都赋为一个很大的数来表示INF，即不可达。

prim算法与Dijkstra算法区别：
Dijkstra算法的数组d[]含义为起点s达到顶点V_i的最短距离。
prim算法的数组d[]含义为顶点V_i与集合S的最短距离

prim算法伪代码

Prim(G, d[])
{
	初始化;
	for(循环n次)
	{
		u = 使d[u]最小的还未被访问的顶点的标号;
		记u已被访问;
		for(从u出发能到达的所有顶点v)
		{
			if(v未被访问 && 以u为中介点使得v与集合S的最短距离d[v]更优)
			{
				将G[u][v]赋值给v与集合S的最短距离d[v];
			}
		}
	}
}

Dijkstra算法和prim算法实际上是相同思路，数组d[]含义不同。

定义MAXV为最大顶点数，INF为一个很大的数字

const int MAXV = 1000; //最大顶点数
const int INF = 100000000; //设INF为一个很大的数

1. 邻接矩阵版

int n, G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数
int d[MAXV]; //顶点与集合S的最短距离
bool vis[MAXV] = {false}; //标记数组，vis[i] == true表示访问。初值均为false
intprim() //默认0号为初始点，函数返回最小生成树的边权之和
{
	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
	d[0] = 0; //只有0号顶点到集合S的距离为0，其余全是INF
	int ans = 0; //存放最小生成树的边权之和
	for(int i = 0; i < n; i++) //循环n次
	{
		int u = -1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
		{
			if(vis[j] == false && d[j] < MIN)
			{
				u = j;
				MIN = d[j];
			}
		}
		//找不到小于INF的d[u]，则剩下的顶点和集合S不连通
		if(u == -1)
			return -1;
		vis[u] = true; //标记u为已访问
		ans += d[u]; //将与集合S距离最小的边加入最小生成树
		for(int v = 0; v < n; v++)
		{
		    //v未访问 && u能到达v && 以u为中介点可以使v离集合S更近
			if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v])
			{
				d[v] = G[u][v]; //将G[u][v]赋值给d[v]
			}
		}
	}
	return ans; //返回最小生成树的边权之和
}

2. 邻接表版

struct Node
{
	int v, dis; //v为边的目标顶点，dis为边权
};
vector<Node> Adj[MAXV]; //图G，Adj[u]存放从顶点u出发可以到达的所有顶点
int n; //n为顶点数，图G使用邻接表实现，MAXV为最大顶点数
int d[MAXV]; //顶点与集合S的最短距离
bool vis[MAXV] = {false}; //标记数组，vis[i] == true表示已访问。初值均为false

int prim() //默认0号为初始点，函数返回最小生成树的边权之和
{
	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
	d[0] = 0; //只有0号顶点到集合S的距离为0，其余全是INF
	int ans = 0; //存放最小生成树的边权之和
	for(int i = 0; i < n; i++) //循环n次
	{
		int u = -1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
		{
			if(vis[j] == false && d[j] < MIN)
			{
				u = j;
				MIN = d[j];
			}
		}
		//找不到小于INF的d[u]，则剩下的顶点和集合S不连通
		if(u == -1)
			return -1;
		vis[u] = true; //标记u为已访问
		ans += d[u]; //将与集合S距离最小的边加入最小生成树
		//只有下面这个for与邻接矩阵的写法不同
		for(int j = 0; j < Adj[u].size(); j++)
		{
			int v = Adj[u][j].v; //通过邻接表直接获得u能到达的顶点v
			if(vis[v] == false && Adj[u][j].dis < d[v])
			{
			    //如果v未访问 && 以u为中介点可以使v离集合S更近
				d[v] = Adj[u][j].dis;
			}
		}
	}
	return ans; //返回最小生成树的边权之和
}

例题

求最小生成树

从V₀开始，依次找到各顶点边权最小的，然后相连

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXV = 1000; //最大顶点数
const int INF = 1000000000; //设INF为一个很大的数

int n, m, G[MAXV][MAXV]; //n为顶点数，MAXV为最大顶点数
int d[MAXV]; //顶点与集合S的最短距离
bool vis[MAXV] = {false}; //标记数组，vis[i]==true表示已访问。初值均为false

int prim() //默认0号为初始点，函数返回最小生成树的边权之和
{
	fill(d, d + MAXV, INF); //fill函数将整个d数组赋为INF
	d[0] = 0; //只有0号顶点到集合S的距离为0，其余全是INF
	int ans = 0; //存放最小生成树的边权之和
	for(int i = 0; i < n; i++) //循环n次
	{
		int u = -1, MIN = INF; //u使d[u]最小，MIN存放该最小的d[u]
		for(int j = 0; j < n; j++) //找到未访问的顶点中d[]最小的
		{
			if(vis[j] == false && d[j] < MIN)
			{
				u = j;
				MIN = d[j];
			}
		}
		//找不到小于INF的d[u]，则剩下的顶点和集合S不连通
		if(u == -1)
			return -1;
		vis[u] = true; //标记u为已访问
		ans += d[u]; //将与集合S距离最小的边加入最小生成树
		for(int v = 0; v < n; v++)
		{
			//v未访问 && u能到达v && 以u为中介点可以使v离集合S更近
			if(vis[v] == false && G[u][v] != INF && G[u][v] < d[v])
			{
				d[v] = G[u][v]; //将G[u][v]赋值给d[v]
			}
		}
	}
	return ans; //返回最小生成树的边权之和
}

int main()
{
	int u, v, w;
	scanf("%d%d", &n, &m); //顶点个数、边数
	fill(G[0], G[0] + MAXV * MAXV, INF); //初始化图G
	for(int i = 0; i < m; i++)
	{
		scanf("%d%d%d", &u, &v, &w); //输入u,v以及边权
		G[u][v] = G[v][u] = w; //无向图
	}
	int ans = prim(); //prim算法入口
	printf("%d\n", ans);
	return 0;
}

//输入数据
6 10 //6个顶点，10条边，以下10行10边
0 1 4 //边0->1与1->0的边权为4，下同
0 4 1
0 5 2
1 2 6
1 5 3
2 3 6
2 5 5
3 4 4
3 5 5
4 5 3

//输出结果
15

前言

在上一篇文章中，我们聊了聊KMP算法，一个极其高效但又非常难以理解（个人看来）的算法，如果有朋友想要深度讨论，欢迎私信。
本篇我们来聊聊prim算法，我最早接触prim算法已经记不清是数据结构课中还是离散数学课中了，但即便科目不同，prim算法还是那个prim算法。
prim算法是一种用于在连通图中获取最小生成树的算法，同样用于获取最小生成树的算法还有Kruskal算法（大家有兴趣同样可以了解了解，但其实二者是比较相似的），prim算法属于贪心算法的一种，至于为什么，或许在分析其过程的时候大家就明白了。
要理解prim算法，大家首先要理解好什么是连通图？什么是最小生成树？这里我们来简单介绍一下，因为这不是我们本次的重点（如果已经有基础的朋友，可以适当跳过）。

• 什么是连通图？，首先理解什么是图？（这里面的学问其实有点大，所以我说咱们就是简单介绍下哈，本篇文章还是对有基础的朋友较友好，因为对于有基础的朋友，我可能是在废话哈哈哈）简单来说，平面内许多点通过一些路径相互连接（不一定要全部连接），就构成了一个图，而根据这些点之间的路径是否有方向，又分为了无向图和有向图。如下图，分别是一种无向图和有向图。
  
  那么？什么是连通图呢？简单来说（只能简单来说了，说多了可以另起一篇文章。。。），就是图中的点通过图中的某些路径（带方向的就必须按照方向来）可以抵达任意一个点。最为简单的模型就是一个地区的许多村落之间的通信，如果每个村庄之间都可以达成通信，就是连通的。

• 最小生成树是什么呢？ 连通图中，每条路径都存在一个权值（理解为距离/成本也行吧，但其实不是这么理解的）。从该连通图出发，寻找一个路径数最少，但每个点之间都可达，就是一个生成树了（专业术语是连通无环子图）。生成树不止一个，而所以生成树中权值之和最小的生成树称为最小生成树。

以上是对最小生成树的简单介绍，如果大家想详细了解一下，可查询资料，这些都不是我们本次的重点。如下给出《算法设计与分析基础》中生成树和最小生成树的定义。

如下为一些例子：

一、算法思想分析

在简单讲解最小生成树的概念后，我们来聊聊prim算法的思想。前面提到过，prim算法是贪心算法的一种，而贪心算法，讲究的就是要极力满足当前最优，这个当前最优正是prim算法的核心思想。
首先，prim算法中存在两个存储空间， 一个用来存放已加入最小生成树的顶点，而另外一个则用来存放还未加入最小生成树中的顶点。 当连通图中所有顶点已放入用于最小生成树的空间中，那么我们最小生成树算法结束！

• 算法开始，起始顶点可随机找或指定一个。将起始顶点先放入已选顶点集合中。
• 在未放入已选顶点集合中查找一条到已选顶点集合中所有点最短（或者是权值最小，这里看自己理解了）的路径（说是一条线或许更合适吧）。刚开始的话，我们已选顶点集合只有一个点！而之后我们会将未加入的顶点一个一个加入已选顶点集合，所以这里的条件必须是已选顶点集合中所有点。显然，在我们找到的这条最短（权值最小）路径的两端的顶点，一个肯定属于还未加入最小生成树中的顶点，另一个肯定属于已加入最小生成树的顶点。将还未加入已选顶点集合的那个点，加入已选顶点集合，本轮任务完成。如果需要路径的，可以将路径记录保存下来。
• 重复第二步，直到所有顶点已加入已选顶点集合，那么，我们的最小生成树就完成了。如果需要计算最小生成树的权值之和，在每一次找到最短路径的时候求一次和即可，需要具体路径的进行标记即可。

接下来，我们举个栗子来做个示范：






该例后续代码将会用到，大家可以自行看看该例。

二、算法效率分析

prim算法的具体效率，是与图的顶点和边数都是有关的。《算法设计与分析基础》中是这么分析的：

以上是一种高级的分析，我们就简单来点吧。
假设总共又n个顶点，那么我肯定有n次比较过程！而在第k次比较过程中，又有n-k个点和另外n-k个顶点相互比较，那么总结起来，那么算法复杂度几乎再n的立方级别。或许有朋友问了，这么算起来，好像也不是很高效哦？n³级别复杂度的确不是很高，但其实prim算法真正效率是介于n²和n³之间的，因为我们如上的分析是一种最坏的情况，就是每个点之间都存在一条路径。
再者，相比于穷举法（也就是蛮力法）来查找最小生成树，prim算法已是大大提升了。《算法设计与分析基础》中这样写到：

三、算法代码

C语言代码

这里我们图的表示用邻接矩阵来表示，具体请看代码极其注释：

/*最小生成树 prim算法 从一个连通图中获取一个最小生成树*/
/*
输入要求：输入一个连通图 存储模式：邻接矩阵表示 0表示不可达  点依次默认命名为a,b,c,d,e,f,g...
例如：n*n数组
6
0 1 0 0 6 5
1 0 1 0 0 4
0 1 0 6 0 4
0 0 6 0 8 5
6 0 0 8 0 2
5 4 4 5 2 0
即为一种输入 实际上为上课讲解时的连通图表示
输出要求： n-1长度数组 包含n-1条路径 ()表示的为m号点到k号点的那条路径 
(1,2) (2,3) (2,6) (6,5) (6,4)
最小生成树权值之和：1+1+4+5+2=13
*/
#include<stdio.h>
#define MAXN 1000
/*二维数组存储 采用邻阶矩阵数据*/
int input[MAXN][MAXN];
int sign[MAXN]= {0}; // 标记sign数组 初始化全为0 ，1表示已经加入已选列表
int prime(int n) {
	int sum=0; // 最小生成树权值之和 初始值为0
	/* 默认从第一个点开始 */
	sign[1]=1;
	int counter=1; // 计算当前状态已加入最小生成树队列的个数
	
	int flagX=-1,flagY=-1,minNodeValue=1000000;
	while(counter!=n) {
		flagX=-1,flagY=-1,minNodeValue=1000000; // 每一次都要初始化 
		/* 每一次循环都是一次贪心 当前局势的一种最优解 */
		for(int i=1; i<=n; i++) {
			if(sign[i]==0) continue; // 如果当前为加入队列 直接下一次循环 其实这是一个笨方法
			for(int j=1; j<=n; j++) {
				// 在查找下一个连接点时 发现这个连接点已经在里面了（或者为0，即不可达） 我们直接跳过 我能说这是一个笨方法么？但似乎只能这样
				if(sign[j]==1||input[i][j]==0) continue;
				if(input[i][j]<minNodeValue){
					// 更小的一个进行标记
					flagX=i;
					flagY=j;
					minNodeValue=input[i][j]; 
				}
			}
		}
		
		/* 一轮查找后 */
			sign[flagY]=1; // 谁该标1 要清楚
			counter++; // 找到加一 
			sum+=input[flagX][flagY]; // 这里其实不用担心指针越界 如果是连通图 在一轮查找下来 肯定能找到一个最小的 
			printf(" (%d,%d) ",flagX,flagY); // 其实我们都知道 flagX flagY 的位置 在这里顺序不重要 
	}
	return sum;
}
int main() {
	/*作为输入的主函数*/
	int n;
	printf("请输入邻接矩阵的维度n："); 
	scanf("%d",&n);
	printf("邻接矩阵：\n");
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=n; j++) {
			scanf("%d",&input[i][j]);
		}
	}
	/*调用函数*/
	int sum = prime(n);
	printf("\n最小生成树权值之和：sum=%d\n",sum);
}

代码中有部分存在取巧，如果大家有任何建议都可私信或留言。

后记

经过一番分析，prim算法的效率似乎是接近n³的，可能偏离了大家的预期。但是一个算法的高效，不是在于它的算法复杂度是多少，而是在于这个算法和解决同样问题的其他算法，相比之下，这个算法是否高效。
简而言之，高效算法是相对的，并不是绝对的。如果在解决最小生成树问题有其他算法比prim算法更为高效，那么那个算法也可以称之为高效算法。
以上只是我的理解，如果大家有其他意见和想法，欢迎留言或私信。

prim算法（普里姆算法）详解

了解了什么是最小生成树后，本节为您讲解如何用普里姆（prim）算法查找连通网（带权的连通图）中的最小生成树。

普里姆算法查找最小生成树的过程，采用了贪心算法的思想。对于包含 N 个顶点的连通网，普里姆算法每次从连通网中找出一个权值最小的边，这样的操作重复 N-1 次，由 N-1 条权值最小的边组成的生成树就是最小生成树。

那么，如何找出 N-1 条权值最小的边呢？普里姆算法的实现思路是：

将连通网中的所有顶点分为两类（假设为 A 类和 B 类）。初始状态下，所有顶点位于 B 类；

选择任意一个顶点，将其从 B 类移动到 A 类；

从 B 类的所有顶点出发，找出一条连接着 A 类中的某个顶点且权值最小的边，将此边连接着的 A 类中的顶点移动到 B 类；

重复执行第 3 步，直至 B 类中的所有顶点全部移动到 A 类，恰好可以找到 N-1 条边。

举个例子，下图是一个连通网，使用普里姆算法查找最小生成树，需经历以下几个过程：

图 1 连通网

1. 将图中的所有顶点分为 A 类和 B 类，初始状态下，A = {}，B = {A, B, C, D, S, T}。

2. 从 B 类中任选一个顶点，假设选择 S 顶点，将其从 B 类移到 A 类，A = {S}，B = {A, B, C, D, T}。从 A 类的 S 顶点出发，到达 B 类中顶点的边有 2 个，分别是 S-A 和 S-C，其中 S-A 边的权值最小，所以选择 S-A 边组成最小生成树，将 A 顶点从 B 类移到 A 类，A = {S, A}，B = {B, C, D, T}。

图 2 S-A 边组成最小生成树

3. 从 A 类中的 S、A 顶点出发，到达 B 类中顶点的边有 3 个，分别是 S-C、A-C、A-B，其中 A-C 的权值最小，所以选择 A-C 组成最小生成树，将顶点 C 从 B 类移到 A 类，A = {S, A, C}，B = {B, D, T}。

图 3 A-C 边组成最小生成树

4. 从 A 类中的 S、A、C 顶点出发，到达 B 类顶点的边有 S-C、A-B、C-B、C-D，其中 C-D 边的权值最小，所以选择 C-D 组成最小生成树，将顶点 D 从 B 类移到 A 类，A = {S, A, C, D}，B = {B, T}。

图 4 C-D 边组成最小生成树

5. 从 A 类中的 S、A、C、D 顶点出发，到达 B 类顶点的边有 A-B、C-B、D-B、D-T，其中 D-B 和 D-T 的权值最小，任选其中的一个，例如选择 D-B 组成最小生成树，将顶点 B 从 B 类移到 A 类，A = {S, A, C, D, B}，B = {T}。

图 5 D-B 边组成最小生成树

6. 从 A 类中的 S、A、C、D、B 顶点出发，到达 B 类顶点的边有 B-T、D-T，其中 D-T 的权值最小，选择 D-T 组成最小生成树，将顶点 T 从 B 类移到 A 类，A = {S, A, C, D, B, T}，B = {}。

图 6 D-T 边组成最小生成树

7. 由于 B 类中的顶点全部移到了 A 类，因此 S-A、A-C、C-D、D-B、D-T 组成的是一个生成树，而且是一个最小生成树，它的总权值为 17。

图 7 最小生成树

普里姆算法的具体实现

接下来，我们将给出实现普里姆算法的 C、Java、Python 程序，程序中有详尽的注释，您可以借助编译器一边运行程序一边观察程序的执行过程，彻底搞清楚普里姆算法是如何找到最小生成树的。

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 C 语言程序：

#include<stdio.h>
#define V 6    // 记录图中顶点的个数
typedef enum { false, true } bool;
//查找权值最小的、尚未被选择的顶点，key 数组记录了各顶点之间的权值数据，visited数组记录着各个顶点是否已经被选择的信息
int min_Key(int key[], bool visited[])
{
    int min = 2147483647, min_index;  //遍历 key 数组使用，min 记录最小的权值，min_index 记录最小权值关联的顶点
    //遍历 key 数组
    for (int v = 0; v < V; v++) {
        //如果当前顶点为被选择，且对应的权值小于 min 值
        if (visited[v] == false && key[v] < min) {
            //更新  min 的值并记录该顶点的位置
            min = key[v];
            min_index = v;
        }
    }
    //返回最小权值的顶点的位置
    return min_index;
}
//输出最小生成树
void print_MST(int parent[], int cost[V][V])
{
    int minCost = 0;
    printf("最小生成树为：\n");
    //遍历 parent 数组
    for (int i = 1; i < V; i++) {
        //parent 数组下标值表示各个顶点，各个下标对应的值为该顶点的父节点
        printf("%d - %d wight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);//由于数组下标从 0 开始，因此输出时各自 +1
        //统计最小生成树的总权值
        minCost += cost[i][parent[i]];
    }
    printf("总权值为：%d", minCost);
}
//根据用户提供了图的信息（存储在 cost 数组中），寻找最小生成树
void find_MST(int cost[V][V])
{    //key 数组用于记录 B 类顶点到 A 类顶点的权值
    //parent 数组用于记录最小生成树中各个顶点父节点的位置，便于最终生成最小生成树
    //visited 数组用于记录各个顶点属于 A 类还是 B 类
    int parent[V], key[V];
    bool visited[V];
    // 初始化 3 个数组
    for (int i = 0; i < V; i++) {
        key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
        visited[i] = false;     // 所有的顶点全部属于 B 类
        parent[i] = -1;         // 所有顶点都没有父节点
    }
    // 选择 key 数组中第一个顶点，开始寻找最小生成树
    key[0] = 0;  // 该顶点对应的权值设为 0
    parent[0] = -1; // 该顶点没有父节点
    // 对于 V 个顶点的图，最需选择 V-1 条路径，即可构成最小生成树
    for (int x = 0; x < V - 1; x++)
    {
        // 从 key 数组中找到权值最小的顶点所在的位置
        int u = min_Key(key, visited);
        // 该顶点划分到 A 类
        visited[u] = true;
        // 由于新顶点加入 A 类，因此需要更新 key 数组中的数据
        for (int v = 0; v < V; v++)
        {
            // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小，表明新顶点的加入，使得类 B 到类 A 顶点的权值有了更好的选择
            if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
            {
                // 更新 parent 数组记录的各个顶点父节点的信息
                parent[v] = u;
                // 更新 key 数组
                key[v] = cost[u][v];
            }
        }
    }
    //根据 parent 记录的各个顶点父节点的信息，输出寻找到的最小生成树
    print_MST(parent, cost);
}
// main function
int main()
{
    int p1, p2;
    int wight;
    int cost[V][V] = { 0 };
    printf("输入图（顶点到顶点的路径和权值)：\n");
    while (1) {
        scanf("%d %d", &p1, &p2);
        //如果用户输入 -1 -1，表示输入结束
        if (p1 == -1 && p2 == -1) {
            break;
        }
        scanf("%d", &wight);
        cost[p1 - 1][p2 - 1] = wight;
        cost[p2 - 1][p1 - 1] = wight;
    }
    // 根据用户输入的图的信息，寻找最小生成树
    find_MST(cost);
    return 0;
}

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Java 程序：

import java.util.Scanner;
public class prim {
    static int V = 6;
    public static int min_Key(int []key,boolean []visited) {
        //遍历 key 数组使用，min 记录最小的权值，min_index 记录最小权值关联的顶点
        int min = 2147483647,min_index = 0;
        //遍历 key 数组
        for (int v = 0; v < V; v++) {
            //如果当前顶点为被选择，且对应的权值小于 min 值
            if (visited[v] == false && key[v] < min) {
                //更新  min 的值并记录该顶点的位置
                min = key[v];
                min_index = v;
            }
        }
        //返回最小权值的顶点的位置
        return min_index;  
    }
  
    public static void print_MST(int []parent, int [][]cost) {
        int minCost = 0;
        System.out.println("最小生成树为：");
        //遍历 parent 数组
        for (int i = 1; i < V; i++) {
            //parent 数组下标值表示各个顶点，各个下标对应的值为该顶点的父节点
            System.out.println((parent[i]+1)+" - "+(i+1)+" wight:"+cost[i][parent[i]]);//由于数组下标从 0 开始，因此输出时各自 +1
            //统计最小生成树的总权值
            minCost += cost[i][parent[i]];
        }
        System.out.print("总权值为："+minCost);
    }
    public static void find_MST(int [][]cost) {
        //key 数组用于记录 B 类顶点到 A 类顶点的权值
        //parent 数组用于记录最小生成树中各个顶点父节点的位置，便于最终生成最小生成树
        //visited 数组用于记录各个顶点属于 A 类还是 B 类
        int []parent = new int[V];
        int []key = new int[V];
        boolean []visited=new boolean[V];
        // 初始化 3 个数组
        for (int i = 0; i < V; i++) {
            key[i] = 2147483647;    // 将 key 数组各个位置设置为无限大的数
            visited[i] = false;     // 所有的顶点全部属于 B 类
            parent[i] = -1;         // 所有顶点都没有父节点
        }
        // 选择 key 数组中第一个顶点，开始寻找最小生成树
        key[0] = 0;  // 该顶点对应的权值设为 0
        parent[0] = -1; // 该顶点没有父节点
        // 对于 V 个顶点的图，最需选择 V-1 条路径，即可构成最小生成树
        for (int x = 0; x < V - 1; x++)
        {
            // 从 key 数组中找到权值最小的顶点所在的位置
            int u = min_Key(key, visited);
            // 该顶点划分到 A 类
            visited[u] = true;
            // 由于新顶点加入 A 类，因此需要更新 key 数组中的数据
            for (int v = 0; v < V; v++)
            {
                // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小，表明新顶点的加入，使得类 B 到类 A 顶点的权值有了更好的选择
                if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
                {
                    // 更新 parent 数组记录的各个顶点父节点的信息
                    parent[v] = u;
                    // 更新 key 数组
                    key[v] = cost[u][v];
                }
            }
        }
        //根据 parent 记录的各个顶点父节点的信息，输出寻找到的最小生成树
        print_MST(parent, cost);
    }
    public static void main(String[] args) {
        int [][]cost = new int[V][V];
        System.out.println("输入图（顶点到顶点的路径和权值)：");
        Scanner sc = new Scanner(System.in);
        while (true) {
            int p1 = sc.nextInt();
            int p2 = sc.nextInt();
          //  System.out.println(p1+p2);
            if (p1 == -1 && p2 == -1) {
                break;
            }
            int wight = sc.nextInt();
            cost[p1-1][p2-1] = wight;
            cost[p2-1][p1-1] = wight;
        }
        // 根据用户输入的图的信息，寻找最小生成树
        find_MST(cost);
    }
}

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Python 程序：

V = 6     #图中顶点的个数
cost = [[0]*V for i in range(V)]
print("输入图（顶点到顶点的路径和权值)：")
while True:
    li = input().split()
  
    p1 = int(li[0])
    p2 = int(li[1])
    if p1 == -1 and p2 == -1:
        break
    wight = int(li[2])
    cost[p1-1][p2-1] = wight
    cost[p2-1][p1-1] = wight
#查找权值最小的、尚未被选择的顶点，key 列表记录了各顶点之间的权值数据，visited列表记录着各个顶点是否已经被选择的信息
def min_Key(key,visited):
    #遍历 key 列表使用，min 记录最小的权值，min_index 记录最小权值关联的顶点
    min = float('inf')
    min_index = 0
    #遍历 key 列表
    for v in range(V):
        #如果当前顶点为被选择，且对应的权值小于 min 值
        if visited[v] == False and key[v]<min:
            #更新  min 的值并记录该顶点的位置
            min = key[v]
            min_index=v
    #返回最小权值的顶点的位置
    return min_index
#输出最小生成树
def print_MST(parent,cost):
    minCost=0
    print("最小生成树为：")
    #遍历 parent 列表
    for i in range(1,V):
        #parent 列表下标值表示各个顶点，各个下标对应的值为该顶点的父节点
        print("%d - %d wight:%d"%(parent[i]+1, i+1, cost[i][parent[i]]))
        #统计最小生成树的总权值
        minCost = minCost + cost[i][parent[i]];
    print("总权值为：%d"%(minCost))
#根据用户提供了图的信息（存储在 cost 列表中），寻找最小生成树
def find_MST(cost):
    #key 列表用于记录 B 类顶点到 A 类顶点的权值
    #parent 列表用于记录最小生成树中各个顶点父节点的位置，便于最终生成最小生成树
    #visited 列表用于记录各个顶点属于 A 类还是 B 类
    parent = [-1]*V
    key = [float('inf')]*V
    visited = [False]*V
    # 选择 key 列表中第一个顶点，开始寻找最小生成树
    key[0] = 0
    parent[0]= -1
    # 对于 V 个顶点的图，最需选择 V-1 条路径，即可构成最小生成树
    for x in range(V-1):
        # 从 key 列表中找到权值最小的顶点所在的位置
        u = min_Key(key,visited)
        visited[u] = True
        # 由于新顶点加入 A 类，因此需要更新 key 列表中的数据
        for v in range(V):
            # 如果类 B 中存在到下标为 u 的顶点的权值比 key 列表中记录的权值还小，表明新顶点的加入，使得类 B 到类 A 顶点的权值有了更好的选择
            if cost[u][v] !=0 and visited[v] == False and cost[u][v] < key[v]:
                # 更新 parent 列表记录的各个顶点父节点的信息
                parent[v] = u
                # 更新 key 列表
                key[v] = cost[u][v]
    # 根据 parent 记录的各个顶点父节点的信息，输出寻找到的最小生成树
    print_MST(parent,cost);
find_MST(cost)

图 1 连通网中的顶点 A、B、C、D、S、T 分别用 1~6 的数字表示，上面程序的运行结果均为：

输入图（顶点到顶点的路径和权值)：
1 5 7
1 3 3
5 3 8
1 2 6
2 3 4
2 4 2
3 4 3
2 6 5
4 6 2
-1 -1
最小生成树为：
4 - 2 wight:2
1 - 3 wight:3
3 - 4 wight:3
1 - 5 wight:7
4 - 6 wight:2
总权值为：17