第十二章最小生成树 路;连通图;圈。 树:连通,且不含圈。 个树中:点个数减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)';