请分别用Prim算法和Kruskal算法构造以下网络的最小生成树 并求出该树的代价。
回答
共1条回复-
(1)用Prim算法构造最小生成树: ①n=8,只有顶点V 0 在最小生成树中。 mst[7]={{0,1,2},{0,2,3},{0,3,∞},{0,4,∞},{0,5,∞},{0,6,∞},{0,7,∞}} 这里的mst[]中每个元素{i,j,w}对应图中权为w的一条边。 ②在mst[0]到mst[6]找出权值最小的边mst[0],即(V 0 ,V 1 ),将顶点V 1 及边加入到最小生成树中。 ③调整mst[1]到mst[6],得到 mst[7]={{0,1,2},{0,2,3},{1,3,2},{0,4,∞},{0,5,∞},{0,6,∞},{0,7,∞}} 这里的黑体{0,1,2}表示该元素对应的边已经在最小生成树中。 ④在mst[1]到mst[6]找出权值最小的边mst[2],即(V 1 ,V 3 ),将顶点V 3 及边加入到最小生成树中。 ⑤调整mst[2]到mst[6],得到 mst[7]={{0,1,2},{1,3,2},{3,2,1),{3,4,2},{3,5,4},{0,6,∞},{0,7,∞}} 得到的最小生成树如下图所示: (2)用Kruskal算法构造最小生成树 集合E中按权递增顺序排列为:(V 2 ,V 3 ),(V 4 ,V 5 ),(V 5 ,V 7 ),(V 6 ,V 7 ),(V 0 ,V 1 ),(V 1 ,V 3 ),(V 3 ,V 4 ),(V 4 ,V 6 ),(V 5 ,V 6 ),(V 0 ,V 2 ),(V 3 ,V 5 )。 ①初始时,最小生成树为只有7个顶点的非连通图。 ②边(V 2 ,V 3 )的两个顶点分别属于两个连通分量,将边(V 2 ,V 3 )加入到最小生成树中。 ③同理,将边(V 4 ,V 5 ),(V 5 ,V 7 ),(V 6 ,V 7 ),(V 0 ,V 1 ),(V 1 ,V 3 ),(V 3 ,V 4 )加入到最小生成树中。 得到的最小生成树如下图所示:

