克鲁斯卡尔算法作业

题目：利用克鲁斯卡尔算法构造一棵最小生成树姓名：吴新华学号：20010155 班级试0101 完成日期：2003-6-2

一、需求分析

1.问题的描述：假设有n个城市之间建立通信

网，则连通n个城市只需n-1条线路。这里

自然考虑怎样建立这n-1条路是总费用最

省。

2.把这n个城市抽象成一个连通网，网的顶点

表示各个城市，顶点与顶点之间的边表示通

信线路，赋予边上的权值表示相应的代价。

3.本程序的目的是要建立一棵生成树使总费

用最少

二、概要设计

1.抽象数据类型定义如下

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

2.主程序

void main()

{

变量定义及初始化；

函数调用并输出结果；

}

3.本程序的模块调用关系

三、详细设计

1.顶点、边和图的类型

typedef struct GTnode{

TElemtype data ; /*顶点的数据域*/

int parent ;/*双亲的位置域*/

}GTnode; 结点结构类型

typedef struct Gedge{

int fromvex; /*边的始点位置域*/

int endvex ; /*边的终点位置域*/

int weight ; /*边的权值域*/

int tags ; /*边的访问标志域*/

}Arclist; /*边的结构类型*/ typedef struct Graph{

GTnode vexlist;/*顶点数组*/

Arclist gelist; /*边集数组*/

int vexnum, edgnum; /*顶点和边总数*/

}graph; /*图数据结构类型*/ 图的基本操作：

void CreateGraph (Graph *g)

{/*创建图并初始化连通分支，初始化边集*/ int n,e; cin>>n>>e;/*输入顶点总数及边总数*/ 为图申请空间；

for (i=0;i

{/*初始化顶点序列*/

cin>>g->vexlist[i].data;