武汉理工大学 信息工程学院 数据结构ch 图最小生成树.pptx

《武汉理工大学 信息工程学院 数据结构ch 图最小生成树.pptx》由会员分享，可在线阅读，更多相关《武汉理工大学 信息工程学院 数据结构ch 图最小生成树.pptx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、7.4.1 无向图的连通分量和生成树若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点；若图是非连通的或非强连通图，则需从图中多个顶点出发搜索访问而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为每个连通分量中的顶点集。第1页/共21页DEABCFJLMGHIKDEGHIKABCFJLM第2页/共21页 深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。生生成成树树：是是一一个个极极小小连连通通子子图图，它它含含有有图图中全部顶点，但只有中全部顶点，但只有n-1n-1条边。条边。由

2、深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。见下页无向图G7的两种生成树。第3页/共21页第4页/共21页例1：画出下图的生成树DFS生成生成树树v0v1v2v4v4v3邻接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生成生成树树v0v1v3v2v4无向连通图无向连通图第5页/共21页2生成森林 若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有 n 个顶点，m 个连通分量或强连通分

3、量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。第6页/共21页DEABCFJLMGHIK例2：画出下图的生成森林（或极小连通子图）求解步骤：求解步骤：Step1:Step1:先求出邻接矩阵或邻接表；先求出邻接矩阵或邻接表；Step2:Step2:写出写出DFSDFS或或BFSBFS结果序列；结果序列；Step3:Step3:画出对应子图或生成森林。画出对应子图或生成森林。这是一个无向非连通图这是一个无向非连通图（参见教（参见教材材P170-171P170-171例）例）下面选用邻接表方式来

4、求深度优先搜索生成森林下面选用邻接表方式来求深度优先搜索生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林注：亦可由邻接矩阵或邻接表直接画出生成森林第7页/共21页115 5M12L11K10J9I8H7G6F5E4D3C2B1A01201200437810661011126709121911112294710811DEGHIK子图子图1：再写出再写出DFS结果（结果（3次）次）ABMJLCFDEGHKIABCFJLM先写出邻接表（或邻接矩阵）：先写出邻接表（或邻接矩阵）：子图子图2：子图子图3：最小连最小连通！通！第8页/共21页DEGHIK子图子图(或连通分量或连通分量)ABCFJLMAB

5、CFJLMDEGHIK生生成成森森林林第9页/共21页7.4.3 最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；从使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图目标：在网络的多个生成树中，寻找一个在网络的多个生成树中，寻找一个各边权值之和最小各边权值之和最小的生成树。的生成树。构造最小生成树的准则v必须只使用该网络中的必

6、须只使用该网络中的边边来构造最小生成树；来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个顶点；个顶点；v不能使用产生回路的边。不能使用产生回路的边。第10页/共21页欲在欲在n n个城市间建立通信网，则个城市间建立通信网，则n n个城市应铺个城市应铺n-1n-1条线路；但条线路；但因为每条线路都会有对应的经济成本，而因为每条线路都会有对应的经济成本，而n n个城市可能有个城市可能有n(n-n(n-1)/2 1)/2 条线路，那么，条线路，那么，如何选择如何选择n n1 1条线路，使总费用最少？条线路，使总费用最少？典型用途：数学模型

7、：数学模型：顶点表示城市，有n n个；边表示线路，有n n1 1条；边的权值表示线路的经济代价；连通网表示n n个城市间通信网。显然此连通网是一个显然此连通网是一个生成树！生成树！问题抽象：问题抽象：n个顶点的生成树很多，需要从中选一棵个顶点的生成树很多，需要从中选一棵代价最小代价最小的生成树，即该树的生成树，即该树各边的代价之和各边的代价之和最小。此树便称为最小生成树最小。此树便称为最小生成树MST(Minimum cost Spanning Tree)第11页/共21页16543271317918127524101564325791013第12页/共21页下面仅讨论无向网的最小生成树问题。

8、普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离,使之保持最小，再重复此过程，直到W为空集止。求解过程参见下页图。普里姆算法第13页/共21页例1654326513566425131163141643142116432142516543214253Prim算法构造最小生成树演示第14页/共21页假设开始顶点就选为顶点1，故首先有U=1，W=2，3，4，5，6i

9、123456closesti111111lowcosti 0615 closest用于存放顶点序号lowest存放权值第15页/共21页i123456closesti131133lowcosti 0505 54 i123456closesti131633lowcosti 0502 50 第16页/共21页i123456closesti131633lowcosti 050050i123456closesti131623lowcosti 000030 i123456closesti131623lowcosti 000000 第17页/共21页1 克鲁斯卡尔算法基本思想克鲁斯卡尔算法基本思想克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。例如，对上图中无向网，用克鲁斯卡尔算法求最小生成树的过程见下图。克鲁斯卡尔（kruskal）算法第18页/共21页克鲁斯卡尔算法构造最小生成树演示第19页/共21页作业请对以下的无向带权图，分别用普里姆算法和克鲁斯卡尔算法求其最小生成树，写出如讲义中的每一步的示意图。第20页/共21页感谢您的观看！第21页/共21页