623最小生成树 有n个乡村,眢村间道路的长度是已知的,如何敷设光 缆线路使n个乡村连通且总长度最短 显然,这要求在已知边长度的网路图中找最小生成树 最小生成树的算法 Kruskal算法:将图中所有边按权值从小到大排列,依次 选所剩最小的边加入边集T,只要不和前面加入的边构 成回路,直到T中有n-1条边,则T是最小生成树 Kruskal算法基于下述定理 定理3指定图中任一点v,如果v是距v最近的相邻节点, 则关联边e;必在某个最小生成树中。 推论将网路中的节点划分为两个不相交的集合吃和V2, V2=VV,则V和V2权值最小的边必定在某个最小生 成树中
11 6.2.3 最小生成树 • 有n 个乡村，各村间道路的长度是已知的，如何敷设光 缆线路使 n 个乡村连通且总长度最短 • 显然，这要求在已知边长度的网路图中找最小生成树 最小生成树的算法： • Kruskal 算法：将图中所有边按权值从小到大排列，依次 选所剩最小的边加入边集 T，只要不和前面加入的边构 成回路，直到 T 中有 n−1 条边，则 T 是最小生成树 • Kruskal 算法基于下述定理 定理 3 指定图中任一点vi，如果 vj 是距 vi 最近的相邻节点， 则关联边 eij 必在某个最小生成树中。 推论 将网路中的节点划分为两个不相交的集合V1和V2， V2=V−V1，则V1和V2间权值最小的边必定在某个最小生 成树中
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中