第七图 4图的连通性（09）.ppt

例 ：画出下图的生成树 例 ：画出下图的生成树 * * 数据结构 7.1 图的定义和术语 第七章 图 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图的应用 7.4 最小生成树问题 设G=(V,E)为连通图，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T和B，其中T是遍历图过程中走过的边的集合，B是剩余边的集合：T∩B=?,T∪B=E(G)。显然G‘=(V,T)是G的一棵生成树。 由深度优先遍历得到的生成树称为深度优先生成树；由广度优先遍历得到的生成树称作广度优先生成树。 一. 生成树 DFS生成树 v0 v1 v2 v4 v4 v3 邻接表 4 3 2 1 0 ^ 1 3 3 4 ^ 1 4 2 ^ 0 v4 v3 v2 v1 v0 2 3 ^ 1 4 2 ^ 0 v0 v2 v1 v4 v3 v0 v1 v2 v4 v4 v3 v0 v1 v2 v4 v4 v3 邻接表 4 3 2 1 0 ^ 1 3 3 4 ^ 1 4 2 ^ 0 v4 v3 v2 v1 v0 2 3 ^ 1 4 2 ^ 0 BFS生成树 v0 v1 v3 v2 v4 v0 v1 v2 v4 v4 v3 结论： 采用不同遍历方法，对一个图从不同顶点出发及所有的存储结构不同均可得到不同的生成树；但它们有很多共性： 生成树的顶点个数与图的顶点个数相同； 具有n个顶点的无向连通图至少有n-1条边，而n个顶点的生成树正好有n-1条边。 生成树中任意两个顶点间的路径是唯一的，若在生成树中任意加一条边必会形成回路；删去一条边定会非连通。 一. 生成树 7.4 最小生成树问题 二. 最小生成树 问题：欲在n个城市间建立通信网，则n个城市应铺n-1条线 路；但因为每条线路都会有对应的经济成本，而n个城 市可能有n(n-1)/2 条线路，那么，如何选择n–1条线 路，使总费用最少？ 顶点———表示城市，有n个； 边————表示线路，有n–1条； 边的权值—表示线路的经济代价； 连通网——表示n个城市间通信网。 数学模型： n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree) 问题抽象： 二. 最小生成树 问题：欲在n个城市间建立通信网，则n个城市应铺n-1条线 路；但因为每条线路都会有对应的经济成本，而n个城 市可能有n(n-1)/2 条线路，那么，如何选择n–1条线 路，使总费用最少？ n个顶点的生成树很多，需要从中选一棵代价最小的生成树，即该树各边的代价之和最小。此树便称为最小生成树MST(Minimum cost Spanning Tree) 问题抽象： 1 6 5 4 3 2 7 13 17 9 18 12 7 5 24 10 1 6 5 4 3 2 7 13 17 9 18 12 7 5 24 10 三.普里姆(Prim)算法 思路: 设N=(V, {E})是连通网，TE是N上最小生成树边的集合。算法从U={v0|v0∈V} ,TE={ }开始，重复执行下列操作：在所有u∈U，v∈V-U的边(u,v) ∈E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V, {TE})为N的最小生成树。 7.4 最小生成树问题 三.普里姆(Prim)算法 伪代码: 初始化：U={v0}(v0为V中任一顶点); TE={} 循环直到U=V为止 1.在所有u=U，v∈V-U的边中找代价最小的边(u,v); 2.TE=TE+{(u,v)}; 3.U=U+{v}; 7.4 最小生成树问题 U={A} V-U={B, C, D, E, F} cost={(A, B)34, (A, C)46, (A, D)∞, (A, E)∞, (A, F)19} 25 12 34 19 26 46 38 17 25 A B E D C F 三.普里姆(Prim)算法 7.4 最小生成树问题 25 12 34 19 26 46 38 17 25 A B E D C F U={A, F} V-U={B, C, D, E} cost={(A, B