第十二章最小生成树 路;连通图;圈。 树:连通,且不含圈。 个树中:点个数减1等于边个数。 若图G中的一个树包含了G的全部顶点(通常会 少一些边),则称该树为图G的一个生成树。 同一个图可能有多个生成树,比较每个生成树的 权,最小者称为最小生成树 求一个给定图的最小生成树: 法一: Kruskal算法 (1)全部边,按权全从小到大排列,取出第一个边 放入集合T (2)从剩余的边中取出权最小的,若该边与T中边 能组成圈,则去掉该边,否则将该边放入集合T (3)重复(2)的工作,直至全部顶点出现,则T 就是最小生成树。 法二:Prim算法 (1)从顶点集V中任取一个顶点,放入集合S (2)考虑VS的点与S的点之间的边,从中取权最 小者放入集合T,对应的点放入S (3)重复(2),直至S包含全部顶点,则T就是最 小生成树 手工做 Kruskal或Prim计算都很容易,但只适用 于规模小(即:顶点数、边数都不大)的图。 例:手工做P189之操练题。 更重要的,还是用机器做: 1.用 Matlab实现 Kruskal算法 输入“边权矩阵”b,顶点数n, 将b的列,按第三行从小到大排序,命令为 b=sorrows(b, 3 关键是如何让机器识别“某个边是否与T中边组 成圈”。这样设计:共有n个顶点1,2,,n,用t表示 顶点i的标记,初始令l1=;集合T中边的任何一组 端点,只要它们沿着T中的路连通就令它们的标记相 同,都等于这组端点的最小标记:对于T外的一条边, “它与T中边组成圈”的充分必要条件是“它的两个 端点的标记相等”。 下面程序(函数M-文件)就是根据“边权矩阵” b用 Kruskal算法给出最小生成数T: function [T, quan]=sypl75hswj(b) n=max(max(b(1: 2, ) m=length(b(1, ) b=sorrows(b, 3), t=l n, k=0; quan=0 for =l: m if t(b(,D))=t(b(2,D)) k=k+1 T(k, =b(j)
第十二章 最小生成树 路；连通图；圈。 树：连通，且不含圈。 一个树中：点个数减 1 等于边个数。 若图 G 中的一个树包含了 G 的全部顶点（通常会 少一些边），则称该树为图 G 的一个生成树。 同一个图可能有多个生成树，比较每个生成树的 权，最小者称为最小生成树。 求一个给定图的最小生成树： 法一：Kruskal 算法 （1）全部边，按权全从小到大排列，取出第一个边 放入集合 T ； （2）从剩余的边中取出权最小的，若该边与 T 中边 能组成圈，则去掉该边，否则将该边放入集合 T ； （3）重复（2）的工作，直至全部顶点出现，则 T 就是最小生成树。 法二：Prim 算法 （1）从顶点集 V 中任取一个顶点，放入集合 S； （2）考虑 V\S 的点与 S 的点之间的边，从中取权最 小者放入集合 T，对应的点放入 S； （3）重复（2），直至 S 包含全部顶点，则 T 就是最 小生成树. 手工做 Kruskal 或 Prim 计算都很容易，但只适用 于规模小（即：顶点数、边数都不大）的图。 例：手工做 P189 之操练题。 更重要的，还是用机器做： 1．用 Matlab 实现 Kruskal 算法 输入“边权矩阵”b，顶点数 n， 将 b 的列，按第三行从小到大排序，命令为 b=sortrows(b’,3)’ 关键是如何让机器识别“某个边是否与 T 中边组 成圈”。这样设计：共有 n 个顶点 1,2,…,n，用 i t 表示 顶点 i 的标记，初始令 t i i = ； 集合 T 中边的任何一组 端点，只要它们沿着 T 中的路连通就令它们的标记相 同，都等于这组端点的最小标记；对于 T 外的一条边， “它与 T 中边组成圈”的充分必要条件是“它的两个 端点的标记相等”。 下面程序（函数 M---文件）就是根据“边权矩阵” b 用 Kruskal 算法给出最小生成数 T： function [T,quan]=syp175hswj(b) n=max(max(b(1:2,:)));m=length(b(1,:)); b=sortrows(b',3)';t=1:n;k=0;quan=0; for j=1:m if t(b(1,j))~=t(b(2,j)) k=k+1; T(k,:)=b(:,j)';
quan=quan+b(3,j) bh=min(t(b(l,),t(b( D)) dbh=max(t(b(l D), t(b(2 )); for Fl n if t(Fbh end end end An end en 如:输入P172图12.1的边权矩阵 b=[l,1,1,2,23,3,42,4.5,3,54,55;8,1,56,7,9,10,3]; 再调用函数文件[ T, quan=spl7hwb) 输出结果 4 6 2 7 quan 17 再做P189之操练题: b=[l,1,1,2,2,3,3,44,55,6,6,7,7,8,9,10;2,8,9,3,9,4,10,5,11, 6,11,118,10,9,10,112,1,8,16,2,3,9,742,1,1,94,7,1,6] IT, quan=syp 175hswj(b) 输出结果 2 6 61 9 8371024 2.用 Matlab实现 Prime算法 Prime算法的函数文件: function [T, quan]=sypl77hswj(a) n=length(a(1, )) h=ones(1, n): h (10: gs=l; k=0; quan=0 gs<I zxInt for F=l:n for Fl
quan=quan+b(3,j); xbh=min(t(b(1,j)),t(b(2,j))); dbh=max(t(b(1,j)),t(b(2,j))); for i=1:n if t(i)==dbh t(i)=xbh; end end end if k==n-1 break end end 如：输入 P172 图 12.1 的边权矩阵 b=[1,1,1,2,2,3,3,4;2,4,5,3,5,4,5,5;8,1,5,6,7,9,10,3]； 再调用函数文件 [T,quan]=syp175hswj(b) 输出结果： T = 1 4 1 4 5 3 2 3 6 2 5 7 quan = 17 再做 P189 之操练题： b=[1,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,9,10;2,8,9,3,9,4,10,5,11, 6,11,7,11,8,10,9,10,11;2,1,8,1,6,2,3,9,7,4,2,1,1,9,4,7,1,6]; [T,quan]=syp175hswj(b) 输出结果： T = 1 8 1 2 3 1 6 7 1 6 11 1 9 10 1 1 2 2 3 4 2 5 11 2 3 10 3 7 10 4 quan = 18 2．用 Matlab 实现 Prime 算法 Prime 算法的函数文件： function [T,quan]=syp177hswj(a) n=length(a(1,:));lh=ones(1,n);lh(1)=0;gs=1;k=0;quan=0; while gs<n zx=Inf; for i=1:n for j=1:n
iflh(i==0&h()=1&a(j)< zX=a(1)), ZXi=1, zxjFj Th(zxj0; k=k+1; gs=gs+1; quan=quan+z T(k, zXi, zxj, ZX d 书P177之例2 a=[o.8,Inf,1,s;8.0,6,Inf,7;nf,6,09,10;1,Inf,9,0,3;5,7,10,3, 0] IT, quan]=sypl77hswj(a) 书P189之Pime算法 clear a=ones(11, 11)Inf for i=1: 11 a(,) a(1,2)=2;a(1,8)=1;a(1,9)8a(2,3=1:a(29)6a(34)2a( 3,10)=3a(4,59;a(4,1l)7;a(56)=4a(5,11)=2;a(6,7)=1 a(6,11)=1;a(7,8)9a(710)=4;a(8,9)7;a(9,10)=1;a(10,11 a(2,1)=2;a(8,1)=1;a(9,1)=8a(3,2)=1a(9,2)=6;a(4,3)=2;a( 10,3)=3a(54)=9,a(114)=7;a(6,5)4;a(11,5)=2a(7,6)=1 a(116)=1a(8,7)=9;a(10,7)4;a(98=7;a(10,9)=1a(11,10 )=6; IT, quan=syp l77hswj(a)
if lh(i)==0&lh(j)==1&a(i,j)<zx zx=a(i,j);zxi=i;zxj=j; end end end lh(zxj)=0;k=k+1;gs=gs+1;quan=quan+zx; T(k,:)=[zxi,zxj,zx]; end 书 P177 之例 2： clear a=[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,quan]=syp177hswj(a) 书 P189 之 Prime 算法： clear a=ones(11,11)*Inf; for i=1:11 a(i,i)=0; end a(1,2)=2;a(1,8)=1;a(1,9)=8;a(2,3)=1;a(2,9)=6;a(3,4)=2;a( 3,10)=3;a(4,5)=9;a(4,11)=7;a(5,6)=4;a(5,11)=2;a(6,7)=1; a(6,11)=1;a(7,8)=9;a(7,10)=4;a(8,9)=7;a(9,10)=1;a(10,11 )=6; a(2,1)=2;a(8,1)=1;a(9,1)=8;a(3,2)=1;a(9,2)=6;a(4,3)=2;a( 10,3)=3;a(5,4)=9;a(11,4)=7;a(6,5)=4;a(11,5)=2;a(7,6)=1; a(11,6)=1;a(8,7)=9;a(10,7)=4;a(9,8)=7;a(10,9)=1;a(11,10 )=6; [T,quan]=syp177hswj(a)
