普里姆算法图文详解
- 作者: 媳妇等我以后给你一个家i
- 来源: 51数据库
- 2022-09-23
普里姆算法用于在连通图中寻找最小生成树，该算法的实现采用了贪心的策略。
连通图指的是各个顶点之间至少存在一条通路的无向图。
对于给定的连通图，普里姆算法寻找最小生成树的过程是：
将图中的所有顶点分为 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<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;
}
如下为普里姆算法寻找最小生成树的 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]<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
