kal 算法求图 1 的最小生成树。(要求写出具体过程)( 10分) 解:根据每条边权的大小进行排序后得到如下生成树的求解过程: (1) v 2v 4, (2) v 2v 4,v 5v 7, (3) v 2v 4,v 5v 7,v 6v 8, (4) v 2v 4,v 5v 7,v 6v 8,v 1v 3, (5) v 2v 4,v 5v 7,v 6v 8,v 1v 3,v 3v 4, (6) v 2v 4,v 5v 7,v 6v 8,v 1v 3,v 3v 4,v 4v 5, (7) v 2v 4,v 5v 7,v 6v 8,v 1v 3,v 3v 4,v 4v 5,v 7v 8. 则最小生成树如下所示,权重为 11。(3 )利用 Prim 算法求图 1 的最小生成树。(要求从结点 v 1 开始,并写出具体过程) ( 10分) 解:设图 1 中全体顶点组成的集合为 V.利用 Prim 算法得到下表: 已经落在生成树上尚未落在生成点集 A至点集 B对应的边树权的点的集合 A树上的点的集合 B 的最短距离(避圈) v 1v 2 ,...,v 82(v 1 ,v 3)2 v 1 ,v 3v 2,v 4 ...,v 82 (v 3 ,v 4)4 v 1 ,v 3 ,v 4v 2 ,v 5, ..., v 81 (v 4 ,v 2)5 v 1 ,v 3 ,v 4 ,v 2v 5, ... ,v 82 (v 4 ,v 5)7 v 1 ,v 3 ,v 4 ,v 2 ,v 5v 6, ... ,v 81 (v 5 ,v 7)8 v 1 ,v 3 ,v 4 ,v 2 ,v 5 ,v 7v 6 ,v 82 (v 7 ,v 8) 10 v 1 ,v 3 ,v 4 ,v 2 ,v 5 ,v 7 ,v 8v 61 (v 6 ,v 8) 11 ……(9分) 从而根据第四列中的边得到最小生成树为……(
全文预览
