Page 219 - 数学建模算法与应用

第八章 图与网络模型及方法应用

聚类分析：在机器学习和数据挖掘中，最小生成树可以用于聚类分析，通过
构建最小生成树来识别数据点之间的相似性。

5. 经济学与金融
投资组合优化：在金融领域，最小生成树可以用于优化投资组合，通过构建
最小生成树来确定最优的投资组合配置，以最小化风险。
市场分析：在市场分析中，最小生成树可以用来分析市场的连接性和依赖关
系，帮助制定更有效的市场策略。

6. 生物信息学
基因网络：在生物信息学中，最小生成树可以用于构建基因网络，通过最小
生成树来识别基因之间的相互作用关系。

蛋白质结构：在蛋白质结构预测中，最小生成树可以用来确定蛋白质分子的
最优结构，以减少能量消耗。
Kruskal 算法如下：
1. 选 e1ÎE(G) ，使得 w(e1 )= min 。
2. 若 e1，e2 ，…，ei 已选好，则从 E(G) － {e1，e2 ，…，ei} 中选取 ei ＋

1 ，使得
① G[{e1，e2 ，…，ei ，ei+1}] 中无圈，且
② w(ei ＋ 1 )=min 。

3. 直到选得 ev-1 为止。
例 用 Kruskal 算法构造例 3 的最小生成树。
我们用 index2×n 存放各边端点的信息，当选中某一边之后，就将此边对应
的顶点序号中较大序号 u 改记为此边的另一序号 v ，同时把后面边中所有序号为
u 的改记为 v 。

此方法的几何意义是：将序号 u 的这个顶点收缩到 v 顶点，u 顶点不复存在。
后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被
选取的资格。

Matlab 程序如下：
clc；clear；
a(1，2)=50； a(1，3)=60； a(2，4)=65； a(2，5)=40；
a(3，4)=52；a(3，7)=45； a(4，5)=50； a(4，6)=30；

209