n个城市最小生成树实验报告.docx

--- - -- -.-word - . -word 资料- 数 据 结 构 课 程 设 计 报 告 起评分 起评分 理论成绩 实践成绩 总成绩 院系： 专业： 班级： 学号： 姓名： 教师： 时间： 目 录 一、设计要求 3 1、问题描述 3 2、功能 3 3、数据 3 二、概述与分析 3 1、图 3 2、邻接矩阵 3 3、生成树 4 4、最小生成树 5 5、最小生成树的操作 5 三、程序设计及分析 6 四、流程图 7 1、模块结构流程图 7 2、Prim 算法流程设计 8 五、测试分析 8 六、总结 10 七、源程序代码 10 --- - -- 一、设计要求： 1、问题描述 构造可以使 n 个城市连接的最小生成树。 2、功能 给定一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。本人采用的是 Prim 算法。 3、数据 城市间的距离网采用邻接矩阵表示（要求至少 6 个城市，10 条边），邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 表示城市间距离网的邻接矩阵（要求至少 6 个城市，10 条边） 二、概述与分析 1、图 图的定义：图G 是有两个集合 V 和 E 组成，记做 G=（V,E），其中 V 是定点的有限集合，记做 V(G)，E 是连接 V 的两个不同的顶点的边的有限集合，记做E(G)。 2、邻接矩阵 邻接矩阵是图的一种存储方法，它是表示顶点之间相邻关系的矩阵。设 …G=(V,E)是具有 n(n>0)个顶点的图，顶点的顺序依次为（v0,v1, ,vn-1）,则 G 的邻 … 接矩阵 A 是 n 阶方阵，其定义如下。 如果 G 是无向图，则 A[i][j]= 1 (vi,vj) ∈E(G) 0 其他 如果 G 是有向图，则 A[i][j]= 1 0 其他 <vi,vj> ∈E(G) 如果 G 是带权无向图，则 A[i][j]= 0 wij ∞ vi≠vj 且 （vi,vj） ∈E(G) vi=vj 其他 如果 G 是带权有向图，则 wij vi≠vj 且 <vi,vj> ∈E(G) A[i][j]= 0 vi=vj ∞ 其他 邻接矩阵的特点如下： 图的邻接矩阵表示是唯一的。 无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想， 在具体存放邻接矩阵是只需要存放上（或下）三角形阵的元素即可。 不带权的有向图的邻接矩阵一般是稀疏矩阵，因此，当图的顶点较多时， 可以采用三元组表的方法存储邻接矩阵。 对于无向图，邻接矩阵的第i 行（或第i 列）非零元素（或非∞元素）的个数正好是第 i 个顶点 Vi 的度。 对于有向图，邻接矩阵的第i 行（或第i 列）非零元素（或非∞元素）的 个数正好是第 i 个顶点 vi 的出度（或入度）。 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行和按列对每个元素进行检测，所花费的时间大家很大，这是用邻接矩阵存储图的局限性。 3、生成树 一个连通图的生成树是一个极小连通图，它含有图中全部顶点，但只有构成一颗树的（n-1）条边。如果在一颗生成树上添加一条边，必定构成一个环：因 为这条边使得它依附的那两个顶点之间有了第 2 条路径。一颗有 n 个顶点的生成树（连通无回路图）有且仅有（n-1）条边，则一定有回路。但是，有（n-1）条边的图不一定都是生成树。 生成树的特点： 1、 连通且无环； 2、 包含原图中的全部 n 个顶点，但只有 n-1 条边； 3、 是原图的极小连通子图； 4、最小生成树 对于一个带权（假定每条边上的权值均大于零的实数）连通无向图 G 中的不同生成树，其每棵树的所有边上的权值之和也可能不同；图的所有生成树中的具有边上的权值之和最小的树成为图的最小生成树。 最小生成树的典型用途： 欲在 n 个城市间建立通信网. n 个城市可能有 n(n-1)/2 条线路，但铺 n-1 条线路即可连通；因为每条线路都会有对应的经济成本，那么，如何选择 n–1 条线路，使总费用最少？ 构造数学模型： 顶点———表示城市，有 n 个； 边————表示线路，有 n–1 条； 边的权值—表示线路的经济代价； 连通网——表示 n 个城市间通信网。 5、最小生成树的操作 1、 Prim 算法：假设 G=(V,E)是连通图，T=(U,TE)为欲构造的最小生成树，初始化 U={u0}，TE 为空，重复以下操作：在所有 u∈U,v∈V-U 的边(u,v) ∈E 中，选择一条权最小的边(u,v)并