实例演示Prim算法运行过程。
01
实例构造
按Prim算法对如图2-27所示的无向连通带权图构造一棵最小生成树。
■图2-27无向连通带权图
假定初始为顶点1，即设定最小生成树T的顶点集合U={1}，V-U={2,3,4,5,6}；
(1)初始化，辅助空间closest和lowcost中的值如表2-15所示。
表2-15集合U、V-U及辅助数组closest、lowcost的初始数据
(2)贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［3］，把它相连的V-U中的顶点3加入到U集合中，把边(closest［3］,3)加入到T中，如图2-28粗线所示。
■图2-28将(1,3)加入到T中示意
检查由于3号店的加入，新添加的连接U和V-U的边：
修正后的数据如表2-16所示。
表2-16第一步贪心选择后集合U、V-U、closest、lowcost数据
(3)贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［6］，把它相连的V-U中的顶点6加入到U集合中，把边(closest［6］,6)加入到T中，如图2-29所示粗线。
■图2-29将(3,6)加入到T中示意
检查由于6号店的加入，新添加的连接U和V-U的边：
修正后的数据如表2-17所示。
表2-17第二步贪心选择后集合U、V-U、closest、lowcost数据
(4)贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［4］，把它相连的V-U中的顶点4加入到U集合中,把边(closest［4］,4)加入到T中，如图2-30粗线所示。
■图2-30将(6,4)加入到T中示意图
检查由于4号店的加入，新添加的连接U和V-U的边；没有添加连接U和V-U的边。数据如表2-18所示。
表2-18第三步贪心选择后集合U、V-U、closest、lowcost数据
(5)贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［2］，把它相连的V-U中的顶点2加入到U集合中，把边(closest［2］,2)加入到T中，如图2-31粗线所示。
■图2-31将(3,2)加入到T中示意
检查由于2号店的加入，新添加的连接U和V-U的边：w(2,5)=3，lowcost［5］=6，w(2,5)lowcost［5］，所以修正lowcost［5］=3，closest［5］=2。
数据如表2-19所示。
表2-19第四步贪心选择后集合U、V-U、closest、lowcost数据
(6)贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［5］，把它相连的V-U中的顶点5加入到U集合中，把边(closest［5］,5)加入到T中，如图2-32粗线所示。
■图2-32将(2,5)加入到T中示意
各数据结构中数据如表2-20所示。
表2-20第五步贪心选择后集合U、V-U、closest、lowcost数据
此时，U=V，算法结束。算法得到的最小生成树如图2-33所示。
■图2-33最小生成树T
实例讲解
算法设计与分析（Python版）
Kruskal算法
选第二大元素的分治算法
快速排序算法中的分治思想
动态规划算法的基本思想
矩阵连乘问题
0-1背包问题的动态规划改进算法——跳跃点算法
子集树模型——0-1背包问题的回溯算法
满m叉树模型——图的m可着色问题的回溯算法
排列树模型——旅行商问题的分支限界法
最大网络流的增广路算法
蒙特卡罗算法
已无更多数据