最小生成树(Kruskal算法).doc

-1- 一、题目描述: 如图所示的赋权图表示某七个城市及预算它们之间的一些某些直接通信道路造价(单位:万元) ,试给出一个设计方案,使得各城市之间既能够通信又使总造价最小并计算其最小值。二、题目分析: 该题即要求赋权图的最小生成树,即可使得各城市间互相通信又使造价费用最小。 1. 生成树及最小生成树定义(1) 生成树的定义入下: 对于有 n 个顶点的无向连通图 G, 把遍历过程中顺序访问的两个顶点之间的路径记录下来, 这样 G 中的 n 个顶点以及由出发点一次访问其余 n-1 个顶点所经过的 n-1 条边就构成了 G 的极小连通子图,也就是 G 的一棵生成树,出发顶点是生成树的根。(2) 下面给出最小生成树的概念: 给定一个连通网络, 要求构造具有最小代价的生成树时, 也即使生成树的各边的权值总和达到最小。把生成树各边的权值总和定义为生成树的权, 那么具有最小权值的生成树就构成了连通网络的最小生成树。 2. 最小生成树的性质构造最小生成树的算法有很多种,其中大多数的算法都利用了最小生成树的一个性质, 简称为 MST 性质: 假设 G= (V,E) 是一个连通网络,U是V 中的一个真子集, 若存在顶点Uu?和顶点)(UVv??的边(u, v) 是一条具有最小权值的边,则必存在 G 的一棵最小生成树包括这条边(u, v)。 3. 常用算法及思想利用该性质构造最小生成树的常用算法主要有: Prim( 普里姆) 算法和 Kruskal( 克鲁斯卡尔) 算法。(1)Prim 算法思想: 设 G= ( V,E )是一个有 n 个顶点的连通图,用 T=(U , TE) 表示要构造的最小生成树,其中U 为顶点集合, TE 为边的集合。则 Prim 算法的具体步骤描述入下: ?初始化:令 U={ ?}, TE={ ?} 。从 V 中取出一个顶点 0u 放入生成树的顶点集 U 中,作为-2- 第一个顶点,此时}){ }, ({ 0?uT?; ?从Uu?,)(UVv??的边(u, v) 中找一条代价最小的边),( **vu ,将其放入 TE 中,并将*v 放入 U 中; ?重复步骤(2), 直至 U=V 为止。此时集合 TE 中必有 n-1 条边,T 即为所要构造的最小生成树。(2)Kruskal 算法思想: 设 G= ( V,E ) 是一个有 n 个顶点的连通图, 则令最小生成树的初始状态为只有 n 个顶点而无任何边的非连通图 T={V,{ ? }}, 图中每个顶点自成一个连通分量。依次选择 E 中的最小代价边,若该边依附于 T 中的两个不同的连通分量,则将此边加入到 T 中;否则,舍去此边而选择下一条代价最小的边。以此类推,直到 T 中所有顶点都在同一连通分量上为止。这时的 T 就是 G 的一棵最小生成树。三、方案解决: 在本题中我们将采用 Kruskal 算法来构造最小生成树。从题目所给赋权图中我们可以得到该图的邻接矩阵为: ???????????????????????036 25 16 941 36 028 00023 25 28 017 000 16 017 0300 9003015 0 400015 020 123 00020 0G 我们将题中的赋权图中 i,j 两个城市之间的造价费用边记为 ijS ,则从小到大排序如下: 顺序 123456789 10 1