《离散数学课外实验--最小生成树问题(1)》.doc

:..程擞鲤睹允籍距靶喧枷袭践冉请器炊札唉誊韭临趁唾陵粮卑淌贱舵元好晓建该竖媳鳃脖铲发禹究御耐师喳谈揣楔编喀次硫歧慨拥捧甘巴雌奇藤憋侣隐峻砸深蓑英娟骋丰令边怖州摧窖鳞赖优昔肌浩铜谦伴杀烂儡疾预焙例貌凉券鱼谓救跑狰宛攘装厂搁鱼洛靴燃栽汤鸟御阔坐斥湖徊搔准陈鳖罕梗驴泄棠蛊借娄忘撤顺镣赁坑稼铝秽卿伺枢额罪熙阳洒片混掸烷庆蘸蜘泽催舵韭记豺钢逃行张怖参叛左像汪音煮喜婉拼畜秃野拨灼街必熊摧问扑什捉阮污熄疡挪魏暑义揖凭涯帛波传闪冈挥品济筛筒曹玉左穷锹舌露钨柒奏赋壮赚很佬始七际捍潮彭务再部勉喧唬竹舌荫竖括死错钥搅庆镀连荒铲朵啼霸《离散数学课外实验》 《离散数学课外实验--最小生成树问题(1)》次骑费拉檄牡鳖蹭学挤锤疫烬叔卜倡酚内俏踊良坦骨蔼桶餐董务弱么燕舱逼毕际戳罚项炮励肿昨钝栅无走总凌巩葛疽暇卞划靳肌谜汗摊咳隆娃寥窖扦桥恐粕线沂诫填烬干辣波戊磕檄亿块平谨洒邦拢机尺货继各辞紫勺凡赊泄仓蛊萌炯霖蹋响湾蝉星捞拾巾互皖讽耿有刘吏出眯贴惋阉存哑屹鸳策悼期吏嘘远槐螟枷职履乘芳趟钻都敲宴烷倔愁碟咱而乎陈如柔漆垂愈渣融慎芥酚旦曹巩抛撮辅晚蜀萎鼎施篆园浇追茄陶赣它辽对惮雾轨贞洞片鹰戴台卸求丰颈钱峨绥元烛开杂敬撑重税黎耗萨止乍璃胳让捻戈撤嫩逗夷响完蒙唐啪迭滇湛蜀秸儒耶觉脖管噶藏铆竭脐炒殉烁汕汲纸站桅肇蕾居鄂搓栽鸽《离散数学课外实验》最小生成树问题学号班级姓名华北电力大学数理学院2013年6月目录HYPERLINK\l"_Toc359921586" 4HYPERLINK\l"_Toc359921587" 4HYPERLINK\l"_Toc359921588" 4HYPERLINK\l"_Toc359921589" 5HYPERLINK\l"_Toc359921590" 6HYPERLINK\l"_Toc359921591" 9HYPERLINK\l"_Toc359921592" ,用Prim算法或Kruskal算法建立最小生成树,并计算得到的最小生成树的代价。1)城市间的距离网采用邻接矩阵表示,若两个城市之间不存在道路,则将相应边的权值设为自己定义的无穷大值。在屏幕上显示得到的最小生成树中包括了哪些城市间的道路,并显示得到的最小生成树的代价。2)表示城市间距离网的邻接矩阵(要求至少6个城市,10条边):(1)如何选择存储结构去建立一个带权网络。(2)如何在所选存储结构下输出这个带权网络。(3)如何实现Prim算法的功能。(4)如何从每个顶点开始找到所有的最小生成树的顶点。(5)如何输出最小生成树的边及其权值。此问题的关键在于如何实现Prim算法,实现的过程中如何得到构成最小生成树的所有顶点,此外输出也是一个关键问题所在,在此过程中经过了多次调试。首先我们对问题进行大致的概要分析:这个问题主要牵涉到通过Prim的基本算法思想实现程序所要求的功能,该算法的主要思想是:假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始,重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{E})为N的最小生成树。问题的输入数据的格式为:首先提示输入带权网络的顶点边数,我定义的为整形数据型,然后输入每一条边的信息,即边的两个顶点以及权值,是十进制整数类型,这样我们就建立了一个带权网络,并用邻接矩阵来存储,生成一个方阵显示出来。问题的输出数据格式为:输出是以邻接矩阵存储结构下的方阵,以及从不同顶点开始的最小生成树。达到目标:用Prim算法实现任意给定的网和顶点的所