【文件属性】：
文件名称：最下生成树问题实习报告
文件大小：45KB
文件格式：DOC
更新时间：2014-01-06 05:06:57
实习报告
最小生成树实习报告
一、需求分析
问题的描述：假设有n个城市之间建立通信网，则连通n个城市只需n-1条线路。这里自然考虑怎样建立这n-1条路是总费用最省。
把这n个城市抽象成一个连通网，网的顶点表示各个城市，顶点与顶点之间的边表示通信线路，赋予边上的权值表示相应的代价。
本程序的目的是要建立一棵生成树使总费用最少
二、概要设计
抽象数据类型定义如下
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}
VR={(u,v)|u,v∈V,w是边(v,w)的权值,∑Wi最小}
基本操作：
void CreateGraph (Graph *g)
操作结果：创建一个图包括两个部分顶点集和边集
int smallweight(Graph *g)
初始条件：图已经存在并且初始化
操作结果：查找权值最小的边并返回它的地址
int samefrom(Graph *g ,int x1,int x2)
初始条件：存在图g和顶点x1,x2
操作结果：判断x1和x2是否属于同一连通分支
void kruskial(Graph *g)
初始条件：连通图g已经存在
操作结果：生成一棵最小生成树
} ADT Graph
主程序
void main()
{
变量定义及初始化；
函数调用并输出结果；
}
本程序的模块调用关系