首页 > 算法 阅读:732

prim算法(普里姆算法)详解,图文并茂

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

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

那么,如何找出 N-1 条权值最小的边呢?普里姆算法的实现思路是:
  1. 将连通网中的所有顶点分为两类(假设为 A 类和 B 类)。初始状态下,所有顶点位于 B 类;
  2. 选择任意一个顶点,将其从 B 类移动到 A 类;
  3. 从 B 类的所有顶点出发,找出一条连接着 A 类中的某个顶点且权值最小的边,将此边连接着的 A 类中的顶点移动到 B 类;
  4. 重复执行第 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}。

S-A 边组成最小生成树
图 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}。

A-C 边组成最小生成树
图 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}。

C-D 边组成最小生成树
图 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}。

D-B 边组成最小生成树
图 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 = {}。

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

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

最小生成树
图 7 最小生成树

普里姆算法的具体实现

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

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的C语言程序:
  1. #include<stdio.h>
  2. #define V 6 // 记录图中顶点的个数
  3. typedef enum { false, true } bool;
  4. //查找权值最小的、尚未被选择的顶点,key 数组记录了各顶点之间的权值数据,visited数组记录着各个顶点是否已经被选择的信息
  5. int min_Key(int key[], bool visited[])
  6. {
  7. int min = 2147483647, min_index; //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
  8. //遍历 key 数组
  9. for (int v = 0; v < V; v++) {
  10. //如果当前顶点为被选择,且对应的权值小于 min 值
  11. if (visited[v] == false && key[v] < min) {
  12. //更新 min 的值并记录该顶点的位置
  13. min = key[v];
  14. min_index = v;
  15. }
  16. }
  17. //返回最小权值的顶点的位置
  18. return min_index;
  19. }
  20.  
  21. //输出最小生成树
  22. void print_MST(int parent[], int cost[V][V])
  23. {
  24. int minCost = 0;
  25. printf("最小生成树为:\n");
  26. //遍历 parent 数组
  27. for (int i = 1; i < V; i++) {
  28. //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
  29. printf("%d - %d wight:%d\n", parent[i] + 1, i + 1, cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
  30. //统计最小生成树的总权值
  31. minCost += cost[i][parent[i]];
  32. }
  33. printf("总权值为:%d", minCost);
  34. }
  35.  
  36. //根据用户提供了图的信息(存储在 cost 数组中),寻找最小生成树
  37. void find_MST(int cost[V][V])
  38. { //key 数组用于记录 B 类顶点到 A 类顶点的权值
  39. //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
  40. //visited 数组用于记录各个顶点属于 A 类还是 B 类
  41. int parent[V], key[V];
  42. bool visited[V];
  43.  
  44. // 初始化 3 个数组
  45. for (int i = 0; i < V; i++) {
  46. key[i] = 2147483647; // 将 key 数组各个位置设置为无限大的数
  47. visited[i] = false; // 所有的顶点全部属于 B 类
  48. parent[i] = -1; // 所有顶点都没有父节点
  49. }
  50. // 选择 key 数组中第一个顶点,开始寻找最小生成树
  51. key[0] = 0; // 该顶点对应的权值设为 0
  52. parent[0] = -1; // 该顶点没有父节点
  53.  
  54. // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
  55. for (int x = 0; x < V - 1; x++)
  56. {
  57. // 从 key 数组中找到权值最小的顶点所在的位置
  58. int u = min_Key(key, visited);
  59. // 该顶点划分到 A 类
  60. visited[u] = true;
  61.  
  62. // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
  63. for (int v = 0; v < V; v++)
  64. {
  65. // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
  66. if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
  67. {
  68. // 更新 parent 数组记录的各个顶点父节点的信息
  69. parent[v] = u;
  70. // 更新 key 数组
  71. key[v] = cost[u][v];
  72. }
  73. }
  74. }
  75. //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
  76. print_MST(parent, cost);
  77. }
  78.  
  79. // main function
  80. int main()
  81. {
  82. int p1, p2;
  83. int wight;
  84. int cost[V][V] = { 0 };
  85. printf("输入图(顶点到顶点的路径和权值):\n");
  86. while (1) {
  87. scanf("%d %d", &p1, &p2);
  88. //如果用户输入 -1 -1,表示输入结束
  89. if (p1 == -1 && p2 == -1) {
  90. break;
  91. }
  92. scanf("%d", &wight);
  93. cost[p1 - 1][p2 - 1] = wight;
  94. cost[p2 - 1][p1 - 1] = wight;
  95. }
  96. // 根据用户输入的图的信息,寻找最小生成树
  97. find_MST(cost);
  98. return 0;
  99. }

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Java 程序:
  1. import java.util.Scanner;
  2.  
  3. public class prim {
  4. static int V = 6;
  5. public static int min_Key(int []key,boolean []visited) {
  6. //遍历 key 数组使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
  7. int min = 2147483647,min_index = 0;
  8. //遍历 key 数组
  9. for (int v = 0; v < V; v++) {
  10. //如果当前顶点为被选择,且对应的权值小于 min 值
  11. if (visited[v] == false && key[v] < min) {
  12. //更新 min 的值并记录该顶点的位置
  13. min = key[v];
  14. min_index = v;
  15. }
  16. }
  17. //返回最小权值的顶点的位置
  18. return min_index;
  19. }
  20. public static void print_MST(int []parent, int [][]cost) {
  21. int minCost = 0;
  22. System.out.println("最小生成树为:");
  23. //遍历 parent 数组
  24. for (int i = 1; i < V; i++) {
  25. //parent 数组下标值表示各个顶点,各个下标对应的值为该顶点的父节点
  26. System.out.println((parent[i]+1)+" - "+(i+1)+" wight:"+cost[i][parent[i]]);//由于数组下标从 0 开始,因此输出时各自 +1
  27. //统计最小生成树的总权值
  28. minCost += cost[i][parent[i]];
  29. }
  30. System.out.print("总权值为:"+minCost);
  31. }
  32. public static void find_MST(int [][]cost) {
  33. //key 数组用于记录 B 类顶点到 A 类顶点的权值
  34. //parent 数组用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
  35. //visited 数组用于记录各个顶点属于 A 类还是 B 类
  36. int []parent = new int[V];
  37. int []key = new int[V];
  38. boolean []visited=new boolean[V];
  39.  
  40. // 初始化 3 个数组
  41. for (int i = 0; i < V; i++) {
  42. key[i] = 2147483647; // 将 key 数组各个位置设置为无限大的数
  43. visited[i] = false; // 所有的顶点全部属于 B 类
  44. parent[i] = -1; // 所有顶点都没有父节点
  45. }
  46. // 选择 key 数组中第一个顶点,开始寻找最小生成树
  47. key[0] = 0; // 该顶点对应的权值设为 0
  48. parent[0] = -1; // 该顶点没有父节点
  49.  
  50. // 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
  51. for (int x = 0; x < V - 1; x++)
  52. {
  53. // 从 key 数组中找到权值最小的顶点所在的位置
  54. int u = min_Key(key, visited);
  55. // 该顶点划分到 A 类
  56. visited[u] = true;
  57.  
  58. // 由于新顶点加入 A 类,因此需要更新 key 数组中的数据
  59. for (int v = 0; v < V; v++)
  60. {
  61. // 如果类 B 中存在到下标为 u 的顶点的权值比 key 数组中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
  62. if (cost[u][v] != 0 && visited[v] == false && cost[u][v] < key[v])
  63. {
  64. // 更新 parent 数组记录的各个顶点父节点的信息
  65. parent[v] = u;
  66. // 更新 key 数组
  67. key[v] = cost[u][v];
  68. }
  69. }
  70. }
  71. //根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
  72. print_MST(parent, cost);
  73. }
  74. public static void main(String[] args) {
  75. int [][]cost = new int[V][V];
  76. System.out.println("输入图(顶点到顶点的路径和权值):");
  77. Scanner sc = new Scanner(System.in);
  78. while (true) {
  79. int p1 = sc.nextInt();
  80. int p2 = sc.nextInt();
  81. // System.out.println(p1+p2);
  82. if (p1 == -1 && p2 == -1) {
  83. break;
  84. }
  85. int wight = sc.nextInt();
  86. cost[p1-1][p2-1] = wight;
  87. cost[p2-1][p1-1] = wight;
  88. }
  89. // 根据用户输入的图的信息,寻找最小生成树
  90. find_MST(cost);
  91. }
  92. }

如下是使用普里姆算法在图 1 所示的连通网中查找最小生成树的 Python 程序:
  1. V = 6 #图中顶点的个数
  2.  
  3. cost = [[0]*V for i in range(V)]
  4. print("输入图(顶点到顶点的路径和权值):")
  5. while True:
  6. li = input().split()
  7. p1 = int(li[0])
  8. p2 = int(li[1])
  9. if p1 == -1 and p2 == -1:
  10. break
  11. wight = int(li[2])
  12. cost[p1-1][p2-1] = wight
  13. cost[p2-1][p1-1] = wight
  14. #查找权值最小的、尚未被选择的顶点,key 列表记录了各顶点之间的权值数据,visited列表记录着各个顶点是否已经被选择的信息
  15. def min_Key(key,visited):
  16. #遍历 key 列表使用,min 记录最小的权值,min_index 记录最小权值关联的顶点
  17. min = float('inf')
  18. min_index = 0
  19. #遍历 key 列表
  20. for v in range(V):
  21. #如果当前顶点为被选择,且对应的权值小于 min 值
  22. if visited[v] == False and key[v]<min:
  23. #更新 min 的值并记录该顶点的位置
  24. min = key[v]
  25. min_index=v
  26. #返回最小权值的顶点的位置
  27. return min_index
  28. #输出最小生成树
  29. def print_MST(parent,cost):
  30. minCost=0
  31. print("最小生成树为:")
  32. #遍历 parent 列表
  33. for i in range(1,V):
  34. #parent 列表下标值表示各个顶点,各个下标对应的值为该顶点的父节点
  35. print("%d - %d wight:%d"%(parent[i]+1, i+1, cost[i][parent[i]]))
  36. #统计最小生成树的总权值
  37. minCost = minCost + cost[i][parent[i]];
  38. print("总权值为:%d"%(minCost))
  39. #根据用户提供了图的信息(存储在 cost 列表中),寻找最小生成树
  40. def find_MST(cost):
  41. #key 列表用于记录 B 类顶点到 A 类顶点的权值
  42. #parent 列表用于记录最小生成树中各个顶点父节点的位置,便于最终生成最小生成树
  43. #visited 列表用于记录各个顶点属于 A 类还是 B 类
  44. parent = [-1]*V
  45. key = [float('inf')]*V
  46. visited = [False]*V
  47. # 选择 key 列表中第一个顶点,开始寻找最小生成树
  48. key[0] = 0
  49. parent[0]= -1
  50. # 对于 V 个顶点的图,最需选择 V-1 条路径,即可构成最小生成树
  51. for x in range(V-1):
  52. # 从 key 列表中找到权值最小的顶点所在的位置
  53. u = min_Key(key,visited)
  54. visited[u] = True
  55. # 由于新顶点加入 A 类,因此需要更新 key 列表中的数据
  56. for v in range(V):
  57. # 如果类 B 中存在到下标为 u 的顶点的权值比 key 列表中记录的权值还小,表明新顶点的加入,使得类 B 到类 A 顶点的权值有了更好的选择
  58. if cost[u][v] !=0 and visited[v] == False and cost[u][v] < key[v]:
  59. # 更新 parent 列表记录的各个顶点父节点的信息
  60. parent[v] = u
  61. # 更新 key 列表
  62. key[v] = cost[u][v]
  63. # 根据 parent 记录的各个顶点父节点的信息,输出寻找到的最小生成树
  64. print_MST(parent,cost);
  65.  
  66. 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