数据结构 最小生成树

《数据结构 最小生成树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、题目最小生成树姓名学号学院专业指导教师一．需求分析1.可以用连通网来表示n个城市以及n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，也就是使总的耗费最少。一棵生成树的代价就是树上各边的代价之和。2.本程序的目的是要建设一个最经济的通信网，根据用户指定的始点和终点输出相应的路径，以及两点之间的距离。在这里城市以及两城市之间的距离都要整型数来代替。3．程序执行的命令包括：（1）利用克鲁斯卡尔算法求最小生成树

2、。（2）构造最小生成树中的连通分量。（3）权值应存放在定义的数组中。（4）输入顶点个数。（5）求出两顶点之间的最小权值边。（6）结束。4．测试数据用户自定义输入顶点个数，并按提示输入两顶点编号及其之间的权值，输入结束后即显示生成的最小生成树。二．概要设计1.抽象数据类型图的定义如下：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R={VR}VR={

3、v，w∈V且P（v，w），表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息}基本操作P：CreateGraph（&G，V，VR）；初始条件：V

4、是图的顶点集，VR是图中弧的集合。操作结果：按V和的VR定义构造图G。DestoryGraph（&G）；初始条件：图G存在。操作结果：销毁图G。LocateVex（G，u）；初始条件：图G存在，u和G中是顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的值。PutVex（&G，v，value）；初始条件：图G存在，v是G中某个顶点。操作结果：对V赋值value，FirstAdjVex（G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：返回v的第

5、一个邻接顶点。若顶点在G中没有顶点，则返回“空”。NextAdjVex（G，v，w）；初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接顶点，则返回“空”。InsertVex（&G，v）；初始条件：图G存在，v和途中顶点有相同特征。操作结果：在图G中添加新顶点v。DeleteVex（&G，v）；初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的弧。InsertArc（&G，v，w）；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中添加弧，若G是无向的

6、，则还增添对称弧。DeleteArc（&G，v，w）；初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除弧，若G是无向的，则还删除对称弧。DFSTravrese（G，Visit（））；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦Visit（）失败，则操作失败。BFSTravrese（G，Visit（））；初始条件：图G存在，Visit是顶点的应用函数。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一

7、次。一旦Visit（）失败，则操作失败。}ADTGraph2．抽象数据类型树的定义如下：ADTTree{数据对象D:D是具有相同特性数据元素的集合。数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}≠，则存在D-{root}的一个划分D1，D2，…，Dm（m>0），对任意j≠k（1≤j,k≤m）有Dj∩Dk=，且对任意的I（1≤i≤m），惟一存在数据元素xi∈Di有∈H；（3）对应于D-{root}的划分

8、，H-{，…，}有惟一的一个划分H1，H2，…，Hm（m＞0），对任意j≠k(1≤j，k≤m)有Hj∩Hk=，且对任意I（1≤i≤m），Hi是Di上的二元关系，（Di，{Hi}）是一棵符合本定义的树，称为跟root的子树。基本操作P：InitTree（&T）；操作结果：构造空树T。DestoryTree（&T）；初始条件：树T存在。操作结果：销毁树T。CreateTree（&T，definition）；初始条件：definition给出树T的定义。操作结果：按definition构造树T。ClearTree（&T）；初始条件：