媳妇等我以后给你一个家i
普里姆算法用于在连通图中寻找最小生成树，该算法的实现采用了的策略。
连通图指的是各个顶点之间至少存在一条通路的无向图。
对于给定的连通图，普里姆算法寻找最小生成树的过程是：
将图中的所有顶点分为 a 类和 b 类，算法执行前，所有顶点都属于 b 类；
从任意顶点出发，同时将此顶点从 b 类划分到 a 类；
从 b 类的所有顶点中，找出到 a 类各个顶点权值最小的一个顶点，将其从 b 类划分到 a 类；
重复执行第 3 步，直至所有顶点全部由 b 类划分到 a 类。
整个过程所历经的路径和顶点，就是一棵最小生成树。
图 1 图存储结构
我们以图 1 所示的连通图为例，如下为普里姆算法寻找最小生成树的过程：
1) 将所有顶点分为两类，类 a={}，类 b={a,b,c,d,s,t}；
2) 假设从 s 顶点出发寻找最小生成树，则 a={s}，b={a,b,c,d,t}。从图 1 可以看出，b 类的所有顶点到顶点 s 权值最小的路径为 (s,a)，所以我们选择 (s,a) 组成最小生成树（如图 2 所示），同时将顶点 a 划分到 a 类。
图 2 寻找最小生成树_过程 1
3) 此时 a={s,a}，b={b,c,d,t}，b 类顶点和 a 类顶点之间的路径有 (s,c)、(a,c)、(a,b)，权值最小的路径为 (a,c)，所以我们选择 (a,c) 组成最小生成树（如图 3 所示），同时将顶点 c 划分到 a 类。
图 3 寻找最小生成树_过程 2
4) 此时 a={s,a,c}，b={b,d,t}，b 类顶点和 a 类顶点之间的路径有 (s,c)、(a,b)、(c,b)、(c,d)，权值最小的路径为 (c,d)，所以我们选择 (c,d) 组成最小生成树（如图 4 所示），同时将顶点 d 划分到 a 类。
图 4 寻找最小生成树_过程 3
5) 此时 a={s,a,c,d}，b={b,t}，b 类顶点和 a 类顶点之间的路径有 (s,c)、(a,b)、(c,b)、(d,b)、(d,t)，权值最小的路径有 2 个，分别是 (b,d) 和 (t,d)。任选其中的一个，比如选择 (b,d)，将顶点 b 划分到 a 类。
图 5 寻找最小生成树_过程 4
6) 此时 a={s,a,c,d,b}，b={t}，b 类顶点 t 和 a 类顶点之间的路径有 (b,t)、(d,t)，权值最小的路径为 (d,t)，因此选择 (d,t) 组成最小生成树（如图 6 所示），同时将顶点 t 划分到 a 类。
图 6 寻找最小生成树_过程 5
7) 此时 a={s,a,c,d,b,t}，b={}，a 类已经包含了图中的所有顶点，查找结束，图 6 即为普里姆算法寻找的最小生成树。
如下为普里姆算法寻找最小生成树的伪代码：
v // 输入图中顶点的总个数
cost[v][v] // 输入图中顶点之间路径的权值
find_mst(cost[v][v]):
parent[v] // 记录最小生成树中各个顶点的父节点的位置
key[v] // 统计未选中的顶点（类b）到已选中的顶点（类a）之间的权值（存储最小的一个）
visited[v] // 记录各个顶点属于类 a 还是类 b
for i<-0 to v:
key[i] <- inf // 将 key 中的各个位置初始化为无限大的值
visited[i] <- false // 初始阶段，所有顶点都位于类 b 中
parent[i] <- -1 // 初始阶段，还没有最小生成树，各个顶点没有父节点
key[0] <- 0 // 从位置为 0 处的顶点出发，寻找最小生成书
parent[0] <- -1 // 位置为 0 的顶点没有父节点
for i <- 0 to v-1: // 最小生成树中的路径总数为顶点数-1
u = min_key(key,visited) // 查找 key 数组中记录的权值最小的顶点所在的下标
visited[u] = true // 将下标为 u 的顶点划分为 a 类中
for v <- 0 to v: // 更新 key 数组中各个 b 类顶点到 a 类顶点的权值
// 如果该顶点属于 b 类，且权值小于当前记录的权值
if visited[v] == false && cost[u][v] < key[v]:
// 更新父节点的信息，同时更新 key 数组记录的权值
parent[v] <- u;
key[v] <- cost[u][v]
return parent // 根据 parent 记录的各个顶点的父节点信息，可以输出最小生成树各个顶点以及相关路径的信息
普里姆算法的具体实现
结合伪代码，如下为普里姆算法寻找最小生成树的 c 语言程序：
#include#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; }
如下为普里姆算法寻找最小生成树的 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);
}
}
如下为普里姆算法寻找最小生成树的 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]
以图 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
