离散数学大作业
-- 最短生成树
班 级： 021052 班
制作人：周萌（ 02105143 ）
西安电子科技大学
2012.12
一 问题介绍
最小生成树 ： 给定一个连通网络 ， 要求构造具有最小代价的生成树时 ， 也即是
生成树各边的权值总和达到最小。把生成树个边的权值总和定义为生成树的权
，
那么具有最小权值的生成树就构成了连通网络的最小生成树 ， 最小生成树可简记
为
MST
。
二 算法介绍
Pr.
(,),,{ 1,2,...,}.
:{ 1 }{2,3,...,}.
,.
,(,),,.
..
im
GVEVn
XYn
xyxXyYyYX
TY
=
==
∈∈
算 法 从 一 个 任 意 顶 点 开 始 生 长 生 成 树
设 为 了 简 便 起 见 取 整 数 集 合
算 法 从 建 立 两 个 顶 点 集 合 开 始 和
接 着 生 长 一 棵 生 成 树 每 次 一 条 边
在 每 一 步 它 找 出 一 条 权 重 最 小 的 边 这 里 并 且 把 从 移 到
这 条 边 添 加 到 中 的 当 前 最 小 生 成 树 边 之 中 重 复 这 一 步 直 到 为 空
三 算法流程
1){};{ 1 };{ 1 }
2){}
3)(,),,
4){}
5){}
6){(,)}
7)
TXYV
whileY
xyxXyY
XXy
YYy
TTxy
endwhile
←←←−
≠
∈∈
←∪
←−
←∪
设 是 最 小 权 重 的 边 其 中
四 实际问题
求图
1
的最短生成树。
五 结果
