文件名称：最下生成树问题实习报告
文件大小：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() { 变量定义及初始化； 函数调用并输出结果； } 本程序的模块调用关系