最小生成树问题

[复制链接]

字体大小: 正常放大

森之张卫东

413 主题	36 听众	1854 积分

升级 85.4%

TA的每日心情

	开心 2019-9-18 21:55

签到天数: 258 天

[LV.8]以坛为家I

群组: 2015国赛冲刺

群组: 2016美赛公益课程

群组: 国赛讨论

群组: 第三届数模基础实训

群组: Matlab讨论组

电梯直达

1^#

发表于 2015-7-14 14:28 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

在一给定的无向图 G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即 (u, v)\in E），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即 T\subseteq E）且为无循环图，使得

w(T) = \sum_{(u,v)\in T} w(u,v)

的 w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。以有线电视电缆的架设为例，若只能沿着街道布线，则以街道为边，而路口为顶点，其

中必然有一最小生成树能使布线成本最低。

下面附上最小生成树算法程序：