图的常用算法——最小生成树.ppt

* * * * ——图的最小生成树 一、图的生成树 在一个连通图G中，如果它的全部顶点和部分边构成一个子图G’ ，且边将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。 同一个图可以有不同 的生成树，但可以证 明：n个顶点的连通图 的生成树必定含有n-1 条边。 要构成这样的图，其基本算法如下： 从图“G”的选取一个顶点放到“G’”中，因只有一个顶点，因此该图是连通的； 以后每加入一个顶点，都要加入以该点为顶点与已连通的顶点之中的一个顶点为端点的一条边，使其既连通而不产生回路，进行n-1次后，就产生G’，在G’中有n个顶点，n-1条边且不产生回路。 二、图的最小生成树 对于一个连通网（带权的图），生成的树不同，每棵树的路径总长度就可能不同，其中具有最小权的树我们称为最小生成树。 研究图的生成树的意义？ 例如城市的通讯系统，网的顶点代表城市，网的边代表城市之间架设通讯线路的造价，求使总的造价最低。 2012-1-10 * 图的最小生成树主要两种方法：prim算法，kruskal算法 三、prim算法（深度优先和广度优先结合算法） prim算法的要点是： （1）设有n个顶点的连通网：G=（V，E），T=（U，TE）是G的最小生成树，其中U是顶点集，TE是T的边集，U、TE开始值为空 （2）原图用邻接矩阵存储 1 2 3 4 5 6 7 ∞ 8 ∞ 5 ∞ ∞ ∞ 8 ∞ 12 3 10 ∞ ∞ ∞ 12 ∞ ∞ 6 2 ∞ 5 3 ∞ ∞ ∞ 7 15 ∞ 10 6 ∞ ∞ 9 ∞ ∞ ∞ 2 7 9 ∞ ∞ ∞ ∞ ∞ 15 ∞ ∞ ∞ （3）prim 算法的实现过程 { 自己到自己为∞ } 1 2 3 4 5 6 7 2012-1-10 * 首先任取一个顶点（V1）进入顶点集合，U={V1}，只要U?V ，就找这样的一条边，它的一个端点已经在树T( vi)中，而将另一个端点且仍在T外，且长度最短的边， 假定为(vi, vj),将该边并入边的集合（TE）， (vj)并入顶点的集合（U）。将该操作重复执行n-1次，直到所有顶点都并入顶点集合中。 问题关键：每次如何从生成树T中到T外的所有边中，快速找出一条最短路径。 分析： 假设已经生成K个顶点，K-1条边的树 ，需要有哪些信誉好的足球投注网站K个顶点与n-k条边的联系，这样时间复杂性为O（k(n-k))。能否降低查找时间则成为该题关键。 (c) 解决方法： 2012-1-10 * 初始化 U={ V1} TE={ } LW={ （V1，V2）8，（V1，V3）∞，（V1，V4）5，（V1，V5）∞，（V1，V6）∞ ,(v1,v7) ∞ } 第一次：U={V1，V4} TE={（V1，V4）5} LW={（V4，V2）3，（V1，V3）∞，（V1，V5）∞，（V4，V6）7，（V4，V7）15 } 第二次：U={ V1，V4，V2} TE={（V1，V4）5，（V4，V2）3 } LW={（V2，V3）12，（V2，V5）10，（V4，V6）7，（V4，V7）15 } * 第三次U={ V1，V4，V2 ，V6 } TE={（V1，V4）5，（V4，V2）3 ，（V4，V6）7 } LW={（V6，V3）2，（V6，V5）9，（V4，V7）15 } 第四次U={ V1，V4，V2 ，V6，V3 } TE= {（V1，V4）5，（V4，V2）3 （V4，V6）7，（V6，V3）2 } LW= {（V3，V5）6，（V4，V7）15 } 第五次U={ V1，V4，V2 ，V6，V3 ，V5 } TE= {（V1，V4）5，（V4，V2）3 ，（V4，V6）7，（V6，V3）2 ，（V3，V5）6 } LW= {（V4，V7）15 2012-1-10 * 第六次 U={ V1，V4，V2