第十二章 最小生成树路；连通图；圈。
树：连通，且不含圈。
一个树中：点个数减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，用表示顶点的标记，初始令； 集合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);
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
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)
树：连通，且不含圈。
一个树中：点个数减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，用表示顶点的标记，初始令； 集合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);
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
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)
