算法设计与分析基础
实验报告
学 院 计算机学院
专 业 软件工程
班 级 08
级
02
班
学 号 3108006888
姓 名 林 佳
指导教师
（2011 年 5 月）
计算机 学院 软件工程 专业 2 班 学号： 3108006888
姓名： 林 佳 协作者：________ 教师评定：
一、实验目的
．掌握贪婪算法 求最小生成树问题。
．掌握贪婪算法 求最小生成树问题。
二、实验内容和要求
． 求最小生成树问题。
． 求最小生成树问题。
三、实验主要仪器设备和材料
．计算机及操作系统： 机，；
．编程环境平台：；
四、实验方法、步骤及结果测试
求最小生成树
算法思想
通过一系列不断扩张的子树来构造一棵最小生成树。
选一初始顶点。每次迭代时，简单贪婪地把不在树中的最近顶点添加到树中。当图的所有顶点都包含在所构造
的树中以后，算法停止。
详细代码
!" #$ %### & '% (## ) $ *
'+, , -./ 0###&(-./ 1&*. #2
3
. 4. #5. #'. #'46
+-/ 5# 7 # +-#2/6 5# 5# 5##*
0&( 7 # -#2. #2/6
8" 9%# 7 # 8"6
'# 7 # '#6
: 5# 5##* "
) 7 6 ; #26 <<
5#-/ 7 )#6
: 0### &( =8 #,$+#
) 7 6 ; #26 <<
) 4 7 6 4 ; #26 4<<
0&(-. 4/ 7 &*#6
) 21 5##*. #,$ ) 5#>? #%#
) 7 . #5 7 6 ; #2 ? 6 <<
3
# 21 5##* 5#
5#-#5/ 7 #6
8 #5 ,#,# #%# "
) 4 7 6 4 ; #26 4<<
3
) 5#-4/ 77 )#
9%#8# 9%##5. 4. 1&*-#5. 4/6
@
9%#6
A # #%#
) 4 7 6 5#-9%#9%#-4// BB 5#-9%#9%#-4//6 4<< 6
#' 7 9%#9%#-4/6
#'4 7 9%#9%#-4/6
0# # 5##*
) 5#-#'/ 77 )#
#5 7 #'6
##
#5 7 #'46
8 # #%# 0### &(
0&(-#'. #'4/ 7 9%#9%#-4/9%#6
0&(-#'4. #'/ 7 0&(-#'. #'4/6
#5# ##,# #%#
9%##5#846
@
# 0&(6
@
求最小生成树
算法思想
算法会先按照权重的非递减顺序对图中的边进行排序。然后从一个空子图开始，扫描这个有序表，试图把列表
中的下一条边加到当前的子图中。当然，这种添加不应导致一个回路，如果产生回路，就把这条边跳过。当图
的所有顶点都包含在所构造的树中以后，算法停止。
详细代码
!" #$ %### & '% (## ) $ *
'+, , -./ 0###&(-./ 1&*. #2
3
. 4. ##%#. #'. #'46
+-/ 5# 7 # +-#2/6 5# 5# 5##*
0&( 7 # -#2. #2/6
8" 9%# 7 # 8"6
'# 7 # '#6
: 5# 5##* "
) 7 6 ; #26 <<
5#-/ 7 )#6
: 0### &( =8 #,$+#
) 7 6 ; #26 <<
) 4 7 6 4 ; #26 4<<
0&(-. 4/ 7 &*#6
8 #%# "
) 7 6 ; #26 <<
) 4 7 <6 4 ; #26 4<<
9%#8# 9%#. 4. 1&*-. 4/6
9%#6
#,$ ) 5#>? #%#
) 7 . ##%# 7 . 4 76 ; #2 ? 6 <<. 4 7 ##%#<
