623最小生成树 最小生成树不一定唯一 定理3推论是一个构造性定理,它指示了找最小生成树 的有效算法 Prim算法:不需要对边权排序,即可以直接在网路图上 操作,也可以在边权矩阵上操作,后者适合计算机运算 边权短阵上的Prim算法 根据网路写出边权矩阵,两点间若没有边,则用∞表示 2、从v1开始标记,在第一行打√,划去第一列; 3、从所有打V的行中找出尚未划掉的最小元素,对该元素画圈 划掉该元素所在列,与该列数对应的行打V; 4、若所有列都划掉,则已找到最小生成树(所有画圈元素所对应 的边):否则,返回第3步。 该算法中,打√行对应的节点在中,未划去的列在中12 6.2.3 最小生成树 • 最小生成树不一定唯一 • 定理 3 推论是一个构造性定理，它指示了找最小生成树 的有效算法 • Prim 算法：不需要对边权排序，即可以直接在网路图上 操作，也可以在边权矩阵上操作，后者适合计算机运算 边权矩阵上的 Prim 算法： 1、根据网路写出边权矩阵，两点间若没有边，则用表示； 2、从 v1 开始标记，在第一行打  ，划去第一列； 3、从所有打  的行中找出尚未划掉的最小元素，对该元素画圈， 划掉该元素所在列，与该列数对应的行打  ； 4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应 的边)；否则，返回第 3 步。 • 该算法中，打  行对应的节点在 V1中，未划去的列在 V2中