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间权值最小的边必定在某个最小生 成树中