图 (三).

Presentation on theme: "图 (三)."— Presentation transcript:

1 图 (三)

2 教学目标 了解生成树的基本概念； 掌握最小生树性质及构造最小生成树的两种不同算法。 2/14

3 生成树 定义：所有顶点均由边连接在一起，但不存在回路的图叫~ 深度优先生成树与广度优先生成树
生成森林：非连通图每个连通分量的生成树一起组成非连通图的~ 说明 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 一个有n个顶点的连通图的生成树有n-1条边 生成树中任意两个顶点间的路径是唯一的 在生成树中再加一条边必然形成回路 含n个顶点n-1条边的图不一定是生成树 G H K I

4 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7
例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 深度优先生成树 V1 V2 V4 V5 V3 V7 V6 V8 V1 V2 V4 V5 V3 V7 V6 V8 广度优先生成树

5 例 A B L M C F D E G H K I J A B L M C F J D E G H K I 深度优先生成森林

6 最小生成树 问题提出 问题分析 1 6 5 4 3 2 7 13 17 9 18 12 24 10 要在n个城市间建立通信联络网，
顶点——表示城市 权——城市间建立通信线路所需花费代价 希望找到一棵生成树，它的每条边上的权值之和（即建立 该通信网所需花费的总代价）最小———最小代价生成树 问题分析 n个城市间，最多可设置n(n-1)/2条线路 n个城市间建立通信网，只需n-1条线路 问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）均连起来，且总耗费 （各边权值之和）最小

7 算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合 初始令U={u0},(u0V), TE=
构造最小生成树方法 方法一：普里姆(Prim)算法 算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合 初始令U={u0},(u0V), TE= 在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0) 将(u0,v0)并入集合TE，同时v0并入U 重复上述操作直至U=V为止，则T=(V,TE)为N的最小生成树 算法实现：图用邻接矩阵表示 对角线元素全为0。构造最小生成树的过程中，若顶点已包含在生成树里，就把其对应的对角线元素置为“1”；若边(vi,vj)已包含进生成树里，就把A[i,j]或A[j,i]位于下三角的一个置为负值

8 例 1 6 5 4 3 2 1 1 3 1 6 3 4 1 6 4 3 2 1 6 4 3 2 5 1 6 5 4 3 2

9 方法二：克鲁斯卡尔(Kruskal)算法
算法思想：设连通网N=(V,E)，令最小生成树 初始状态为只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边 依此类推，直至T中所有顶点都在同一连通分量上为止

10

11 作业 分别给出应用Kruskal和Prim算法构造最小生成树的过程,以及算法的实现。