第8讲最小生成树与最短路应用(第1次课)

1、第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用1第八讲 最小生成树算法应用(上)内容：内容：本讲主要介绍最小生成树算法及实现本讲主要介绍最小生成树算法及实现目的：目的：学习最小生成树算法的学习最小生成树算法的 MATLAB实现实现 要求：要求：能够运用软件直接对小规模最小生成树能够运用软件直接对小规模最小生成树 问题进行求解问题进行求解回顾最小生成树问题所涉及的图的概念和术语回顾最小生成树问题所涉及的图的概念和术语掌握掌握Kruskal算法算法和和Prim算法算法的描述和实现的描述和实现通过范例通过范例,掌握最小生成树问题应用一般过程掌握最小生成树问题应用一般过程第八讲第八讲

2、最小生成树与最小生成树与最短路的应用最短路的应用2最小生成树问题的引入和概述 最小生成树最小生成树问题属于典型的基于图的网络优化问题属于典型的基于图的网络优化问题，树（问题，树（treetree）在图论中是相当重要的一类图，）在图论中是相当重要的一类图，它非常类似于自然界中的树，我们的着眼点在于：它非常类似于自然界中的树，我们的着眼点在于：设计或寻找（设计或寻找（更快地寻找更快地寻找）某种具有最优特性的）某种具有最优特性的最小生成树及其算法。最小生成树及其算法。 在工农业生产、交通运输、通讯和电力领域经在工农业生产、交通运输、通讯和电力领域经常都能看到许多网络，如管道网、公路网、计算常都能看到

3、许多网络，如管道网、公路网、计算机通讯网、输电线网等等。还有许多看不见的网机通讯网、输电线网等等。还有许多看不见的网络，如各种关系网、事物的相互冲突关系等等，络，如各种关系网、事物的相互冲突关系等等，这些网络都可归结为网络最优化问题。这些网络都可归结为网络最优化问题。 最小生成树是具有很多最优特性的一种图，最最小生成树是具有很多最优特性的一种图，最小生成树算法是重要的最优化算法（小生成树算法是重要的最优化算法（p173p173）第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用3最小生成树：最小生成树：在一个在一个加权连通图加权连通图中，总权最小的那棵中，总权最小的那棵生成树生成树

4、加权：加权：边被赋予权重（比如边被赋予权重（比如费用，路程费用，路程.）连通图：连通图：任意两点间都有路径的图（可抵达）任意两点间都有路径的图（可抵达）树：树：没有圈的连通图（圈：路径终点回到起点）没有圈的连通图（圈：路径终点回到起点）生成树：生成树：包括原图所有点的树（属于原图子图）包括原图所有点的树（属于原图子图）最小生成树：最小生成树：所有生成树中权重之和最小的树所有生成树中权重之和最小的树最小生成树的相关概念ACDBACDBACDBADCB第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用4电信局配接电缆问题：电信局配接电缆问题：电信总局要如何配接电缆才能使各电信局能互通电

5、信总局要如何配接电缆才能使各电信局能互通讯息讯息, 但同时令配线经费最低？但同时令配线经费最低？最小生成树问题的应用举例第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用5大公司部门之间的沟通管道：大公司部门之间的沟通管道：最小生成树问题的应用举例第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用6最小生成树问题的描述 要在要在n个城市间建立通信联络网，顶点个城市间建立通信联络网，顶点表示表示城市城市，权权城市间建立通信线路所需花费代价城市间建立通信线路所需花费代价，希望找到一棵生成树，它的每条边上的权值之和希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需

6、花费的总代价）最小（即建立该通信网所需花费的总代价）最小最最小代价生成树小代价生成树（最小生成树）：（最小生成树）： 1654327131791812752410第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用7最小生成树算法- KR图示Kruskal算法和算法和Prim算法，都蕴涵了贪婪法的思想算法，都蕴涵了贪婪法的思想（p174），都属于构造性的方法。此外，最小生），都属于构造性的方法。此外，最小生成树不一定唯一。成树不一定唯一。 Kruskal算法示意图：算法示意图： V1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V612V1V2

7、V4V5V3V6132V1V2V4V5V3V61423V1V2V4V5V3V614253第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用8最小生成树算法- PR图示Prim算法示意图算法示意图：V1V2V4V5V3V66555662134V1V2V4V5V3V61V1V2V4V5V3V614V1V2V4V5V3V6142V1V2V4V5V3V61425V1V2V4V5V3V614253第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用9最小生成树算法- KR演示Kruskal算法动画演示算法动画演示1： 第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用1

8、0最小生成树算法- KR演示Kruskal算法动画演示算法动画演示2： 第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用11最小生成树算法- PR演示Prim算法算法动画演示动画演示1：第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用12最小生成树算法- PR演示Prim算法算法动画演示动画演示2：第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用13最小生成树算法-程序实现 为简便起见，以一个小型的问题为例。假设各为简便起见，以一个小型的问题为例。假设各站点间可以铺设通讯线路进行连接的情况如下图站点间可以铺设通讯线路进行连接的情况如下图所示，所示，顶点

9、顶点为站点，为站点，边边为连接两站点之间的通讯为连接两站点之间的通讯线，线，边权边权为费用。为费用。 我们的目的是找到图我们的目的是找到图中中一个连一个连接所有顶点的具有最小总权数接所有顶点的具有最小总权数(费用费用)的连通子图的连通子图即即最小生成树最小生成树第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用14最小生成树算法-KR程序clearb=1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3; %边权阵边权阵B,i=sortrows(b,3); B=B;m=size(b,2);n=5;t=1:n;k=0;T=;c=0;for

10、i=1:m if t(B(1,i)=t(B(2,i) k=k+1; T(k,1:2)=B(1:2,i); c=c+B(3,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n if t(j)=tmax t(j)=tmin; end end end if k=n-1 break endendT,c第八讲第八讲 最小生成树与最小生成树与最短路的应用最短路的应用15最小生成树算法-PR程序cleara=0 8 inf 1 5; 8 0 6 inf 7; inf 6 0 9 10; 1 inf 9 0 3; 5 7 10 3 0; %带权邻接阵带权邻接阵T=;c=0;v=1;n=5;sb=2:n;for j=2:n b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);endwhile size(T,2)n-1 min,i=min(b(3,:); T(:,size(T,2)+1)=b(:,i); c=c+b(3,i); v=b(2,i); temp=find(sb=b(2,i); sb(t