数据结构课程设计七.pdfVIP

数据结构课程设计七

06120060724035

班级：计本()姓名：魏建平学号：

题目：严慰敏习题实习五第6题，求图的最小生成树问题：若要在n个城市之间建设通信

网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个最小生成树问

题。

一、需求分析

1、利用克鲁斯算法求网的最小生成树，实现抽象数据类型MFSet，以此表示构造生成树

过程中的连通分量。

2、以文本形式输出生成树中各条边以及他们的权植。

3、用邻接矩阵表示法的形式建立图的存储结构。它采用两个数组来表示图：一个用来

存放图的顶点名字，另一个用来存储图中顶点之间关联关系的二维数组。

4、演示程序以用户和计算机的对话框执行，根据对话框所显示的内容，进行输入。最后进行

核对。

5、测试数据：

二、概要设计

1、抽象数据类型图的定义：

ADTGraph

数据对象:—个集合，该集合中的所有元素具有相同的特性。数据关系:

VRR={VR}

VR={x,y|P(x,y)n(x,y€V)}

基本操作：

1):CreateGraph(G):

初始条件：图存在。

G

操作结果：创建图G

2):DestoryGraph(G):

初始条件：图存在。

G

操作结果：销毁图G

3):LocateVertex(G,v):初始条件：图G存在。

操作结果：确定顶点在图中的位置。若图中没有顶点，则函数值为空。

vGGv

4)：GetVertex(G,i):

初始条件：图存在。

G

操作结果：取出图的第个顶点的值。若大于图的顶点数，则函数值为空。

GiiG

5)：FirstAdjVertex(G,v):

初始条件：图存在。

G

操作结果：求图中顶点的第一个邻接点。若无邻接点或图中无顶点,则函数值为空。

GnvGv

6)：NextAdjVertex(G,v,w):

初始条件：图存在。

G

操作结果：一直是图中顶点的某个邻接点，求顶点的下一个邻接点紧跟这后面。若是

wGvv(w)w

v的最后一个邻接点，则函数值为空。

7)：InsertVertex(G,u):

初始条件：图存在。

G

操作结果：在图中增加一个顶点。

Gu

8)：DeleteVertex(G,u):

初始条件：图存在。

G

操作结果：删除图的顶点及其顶点相关联的弧。

Gvv

9)：InsertArc(G,v,w):

初始条件：图存在。

G

操作结果：在图着那个增加一条从顶点到顶点的弧。

G