matlab最小生成树函数graphminspantree

matlab最小生成树函数graphminspantree

在图论中，最小生成树也叫最小支撑树，它的应用很广，比如求一些最优化问题，另外在一些数学建模比赛中也经常出现，因此，小编觉得有必要和大家分享一下它的画法，这样看起来可以更加的直观。在matlab中有个函数是graphminspantree，可以通过这个函数直接画出最小生成树。

这里主要是参照matlab的帮助文档来给大家说明。首先我们打开matlab，这里使用了matlab2014B这个版本。

在命令窗口输入>>helpgraphminspantree

打开graphminspantree的帮助文档。

找到示例，在命令窗口输入>>W = [.41 .29 .51 .32 .50 .45 .38 .32 .36 .29 .21];

W这是生成树“边”的权重。

然后在命令窗口输入>>DG = sparse([1 1 2 2 3 4 4 5 5 6 6],[2 6 3 5 4 1 6 3 4 2 5],W);

需要注意的是，在matlab中sparse是用来产生稀疏矩阵的一个函数，第一个输入矩阵[1 1 2 2 3 4 4 5 5 6 6]必须是从小到大排列，第二个输入矩阵[2 6 3 5 4 1 6 3 4 2 5]与它对应。

这里有个关键的地方需要特别注意，大多数人都是卡在这里，百思不得其解。简单的说就是第一个输入矩阵的最大数和第二个输入矩阵的最大数必须要相等（在这里是6）。

接着输入>>UG = tril(DG + DG')

在matlab中tril是用来提取矩阵下三角矩阵的函数。

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

在matlab中view是用来设置视点的函数。

最后运用graphminspantree函数，输入：

>>[ST,pred] = graphminspantree(UG)

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

最后得到最小生成树。