最小支撑树MST

实验类型：◆验证性实验  ◇综合性实验  ◇设计性实验

实验目的：学会使用Matlab编程求解最小支撑树。

实验内容：1.掌握避圈法、破圈法求最小支撑树的基本原理和方法；2.利用Matlab工具箱graphminspantree实现求最小支撑树。

实验习题：已知六大城市：(Pe)，(N)，(Pa)，(L)，(T)，(M)，它们之间的交通网络数据如下表所示，求最小支撑树。

城市	Pe	T	Pa	M	N	L
Pe	×	13	51	77	68	50
T	13	×	60	70	67	59
Pa	51	60	×	57	36	2
M	77	70	57	×	20	55
N	68	67	36	20	×	34
L	50	59	2	55	34	×

实验原理：

1.matlab中sparse函数和full函数

这对函数可以看做是一对反义词

sparse函数

功能：Create sparse matrix-创建稀疏矩阵

用法1：S=sparse(X)——将矩阵X转化为稀疏矩阵的形式，即矩阵X中任何零元素去除，非零元素及其下标（索引）组成矩阵S。 如果X本身是稀疏的，sparse(X)返回S。

用法2：S = sparse(i,j,s,m,n,nzmax)——由i,j,s三个向量创建一个m*n的稀疏矩阵（上面的B矩阵形式），并且最多含有nzmax个元素。

一些简写的情况：

1）S = sparse(i,j,s,m,n)——nzmax = length(S) ；

2）S = sparse(i,j,s)——使m = max(i) 和 n = max(j)，在S中零元素被移除前计算最大值，[i j s]中其中一行可能为[m n 0]；

3）S = sparse(m,n)——sparse([],[],[],m,n,0)的缩写，生成一个m*n的所有元素都是0的稀疏矩阵。

full函数：

功能：把稀疏矩阵转为全矩阵

A=full(X)——把稀疏矩阵X转换为全矩阵存储形式A。

2.最小生成树：多一条边成环，少一条边不连通（极小连通子图）为生成树，满足上述条件且权值最小即为最小生成树。

3.Kruskal算法（避圈法）关键思想：

1）寻找权值最小的边，若加入生成树不会形成回路，则加入；

2）如果加入的边会形成回路，则舍弃（避圈）；

3）如此循环直到连接了所有点，此时形成的则为最小生成树。

4.破圈法实现最小生成树

在克鲁斯克尔算法基础上，我国著名数学家管梅谷教授于1975年提出了最小生成树的破圈法。

算法过程:

1)先将所有的边按权值进行降序排列；

2)之后对于取出的每一个边来说,判断其连接的两个结点是否具有圈.(即先删除次边,然后判断这两个结点是否连接,之后对删除的边进行恢复)；

3)对于有圈的,将这条边删除,否则,往下查找；

4)算法结束条件:剩下的边=结点数-1。

实验步骤：

1. 上机实验前先编写出程序代码

2. 录入、编辑程序

3. 调适程序至正确运行

4. 记录运行时的输入和输出

5. 对程序做进一步完善

程序代码：

W=input('此程序有关MST，请输入权重矩阵W：');

[i,j,s]=find(W);

ss=[i';j';s'];

dg=sparse(ss(1,:),ss(2,:),ss(3,:));

DG=triu(dg);

UG=tril(DG+DG');

view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))

[ST,pred]=graphminspantree(UG);

view(biograph(ST,[],'ShowArrows','off','ShowWeights','on'))

MSTValue=sum(sum(full(ST)));

ST

实验程序录入界面及程序运行结果界面：

实验总结：

此实验通过用户输入权重矩阵W，表示图中各边的权重。利用find函数获取权重矩阵中非零元素的行列索引和对应的权重值。构造稀疏矩阵dg，并利用triu函数将其转换为上三角稀疏矩阵DG。构造无向图的邻接矩阵UG，并利用biograph函数将其以图形方式展示出来，其中参数'ShowArrows','off'表示不显示箭头，'ShowWeights','on'表示显示边的权重。利用graphminspantree函数计算最小生成树ST，并利用biograph函数将其以图形方式展示出来。计算最小生成树的总权值MSTValue，即所有边权重之和。

通过本次实验，掌握了利用Matlab编程求解最小生成树的方法，并了解了最小生成树在图论中的应用。让我对最小生成树有了一个更深的认识，通过实验自己在慢慢进步，加油！