最小生成树实习报告.doc
5星 · 超过95%的资源 需积分: 25 6 浏览量
2020-01-27
10:32:59
上传
评论 3
收藏 139KB DOC 举报 
最小生成树实习报告
题目：利用克鲁斯卡尔算法求最小生成树
班级： 姓名： 学号： 完成日期：
一． 需求分析
1.问题描述：若要在 n 个城市之间建设通信网络，只需要假设 n-1 条线路即可。
如何以最低的经济代价建设这个通信网，是一个网的最小生成树
问题
2.基本要求: (1)利用克鲁斯卡尔算法求网的最小生成树；
(2)实现用教科书 6.5 节定义的抽象数据类型 MFset，以此结构生成树
过程中的连通分量
(3)以文本形式输出生成树中各条边以及他们的权值。
3.通信线路一旦建立，必然是双向的。因此，构成最小生成树的网一定是无向
图。设图的顶点不超过 30 个，并为简单起见，网中的权值设为<=100 的整数，
可用 C 语言的提供的随机函数产生（但是我实现的时候没有用到随机函数）
二． 概要设计
图的存储使用结构体表示法，即两个存顶点的信息，一个数据存权值然后
把图各边的权值按从小到大排序；然后依次把最小边加入进来，即生成最小生
成树。
克鲁斯卡尔算法：假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网，按照构
造最小成树的过程为：先构造一个只含 n 个顶点，而边集为 空的子图，之后，
从网的边集 E 中选取一条权值最小的边，若该 条边的两个顶点分属不同的树，
则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，
而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图
中含有 n-1 条边为止。
设定图的抽象数据类型：
ADT Node{
数据对象 x， y:是具有相同特性的数据元素的集合,称为点集.
数据关系 dis:
dis={VR}
VR={(x,y)|x,w 属于 V,(x,y)表示 x 和 y 之间存在的路径
基本操作 P:
set(MFSet &S)
操作结果：初始化 S
find_MFset(MFSet &S, int i)
操作结果：确定 i 所在子集，并将 i 至路径上所有结点都变成跟的孩子结点
资源评论
XU美伢2023-07-25对于最小生成树算法，这份报告提供了清晰的解释和实用的示例，非常易于理解。
KerstinTongxi2023-07-25这份实习报告很出色，透露出作者的扎实学术基础和对最小生成树算法的深刻理解。
三山卡夫卡2023-07-25这份实习报告虽然语言简单，但是内容丰富，告诉读者如何应用最小生成树算法解决实际问题。
曹将2023-07-25这个报告详细讲解了最小生成树算法的相关概念，对读者来说是非常有帮助的参考资料。
石悦2023-07-25这个文件很实用，对于初学者来说是一份很好的学习资料，讲解方式简明扼要。
