最小生成树实验报告
- 格式：doc
- 大小：28.50 KB
- 文档页数：3
最小生成树算法的设计与实现
一、实验目的
1、根据算法设计需要, 掌握连通网的灵活表示方法;
2、掌握最小生成树算法，如Prim、Kruskal算法;
3、基本掌握贪心算法的一般设计方法;
4、进一步掌握集合的表示与操作算法的应用.
二、预习与参考
1、认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;
2、设计Kruskal算法实验程序.
[参考数据类型或变量]
typedef NodeNumber int; /* 节点编号 */
typedef CostType int; /* 成本值类型 */
typedef ElemType NodeNumber /* 实型或任意其它元素类型 */
typedef struct { int ElemType; int tag; }NODE;
typedef struct { CostType cost; NodeNumber node1, node2; }EDGE;
NODE set[]={{1,-1},…,{n,-1}}; /* 节点集, n为连通网的节点数 */
EDGE es[ ]={{values of e1},…,{ values of e m}}; /* 边集, m为连通网的边数 */ EDGE st[n-1]; /* 最小生成树的边集 */
[参考子程序接口与功能描述]
int Find(NODE *set, ElemType elem)
功能: 在数组set中顺序查找元素elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的查找算法,返回所在子集的根节点索引.
int Union(NODE *set, ElemType elem1, ElemType elem2)
功能: 应用Find算法首先找到elem1和elem2所在的子集, 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.
void Sort(EDGE *es, int n)
功能: 用任意分类算法将连通图的边集按成本值的非降次序分类.
void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)
功能: 对有n个节点, m条边的连通网, 应用Kruskal算法生成最小生成树, 最小生成树的边存储在数组st中.
void Output(EDGE *st, int n)
功能: 输出最小生成树的各条边.
三、实验要求
上机实验时，一人一组，独立上机。
有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。
四、实验步骤
1、设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;
2、待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成功能模块存盘备用.
五、测试
Input:
6
1 2 6
1 3 1
1 4 5
2 3 5
2 5 6
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6
0 0 0
Putout:
18
六、实验报告要求
1、阐述实验目的和实验内容;
2、阐述Kruskal算法的原理方法;
3、提交实验程序的功能模块;
4、提供测试数据和相应的最小生成树。
七、思考题
1、设计由连通网初始边集数组生成最小堆的算法;
2、设计输出堆顶元素, 并将剩余元素调整成最小堆的算法;
3、针对连通网初始边集最小堆表示, 设计Kruskal算法;
4、采用成本邻接矩阵表示连通网时, 在剩余边中如何实现最小成本边的查找? 采用成本邻接矩阵表示连通网时, 用C语言实现Prim算法.。
