01、实例构造

按Prim算法对如图1所示的无向连通带权图构造一棵最小生成树。

■ 图1 无向连通带权图

假定初始为顶点1，即设定最小生成树T的顶点集合U={1}，V-U={2,3,4,5,6}；

(1) 初始化，辅助空间closest和lowcost中的值如表1所示。

表1 集合U、V-U及辅助数组closest、lowcost的初始数据

(2) 贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［3］，把它相连的V-U中的顶点3加入到U集合中，把边(closest［3］,3)加入到T中，如图2粗线所示。

■ 图2 将(1,3)加入到T中示意

检查由于3号点的加入，新添加的连接U和V-U的边：

修正后的数据如表2所示。

表2第一步贪心选择后集合U、V-U、closest、lowcost数据

(3) 贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［6］，把它相连的V-U中的顶点6加入到U集合中，把边(closest［6］,6)加入到T中，如图3所示粗线。

■ 图3 将(3,6)加入到T中示意

检查由于6号点的加入，新添加的连接U和V-U的边：

修正后的数据如表3所示。

表3 第二步贪心选择后集合U、V-U、closest、lowcost数据

(4) 贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［4］，把它相连的V-U中的顶点4加入到U集合中,把边(closest［4］,4)加入到T中，如图4粗线所示。

■ 图4 将(6,4)加入到T中示意图

检查由于4号点的加入，新添加的连接U和V-U的边；没有添加连接U和V-U的边。数据如表4所示。

表4 第三步贪心选择后集合U、V-U、closest、lowcost数据

(5) 贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［2］，把它相连的V-U中的顶点2加入到U集合中，把边(closest［2］,2)加入到T中，如图5粗线所示。

■ 图5将(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。

数据如表5所示。

表5第四步贪心选择后集合U、V-U、closest、lowcost数据

(6) 贪心选择连接U和V-U的权最小的边，即V-U中lowcost最小的lowcost［5］，把它相连的V-U中的顶点5加入到U集合中，把边(closest［5］,5)加入到T中，如图6粗线所示。

■ 图6 将(2,5)加入到T中示意

各数据结构中数据如表6所示。

表6第五步贪心选择后集合U、V-U、closest、lowcost数据

此时，U=V，算法结束。算法得到的最小生成树如图7所示。

■ 图7 最小生成树T