构造可以使n个城市连接的最小生成树.doc

数据结构 课程设计报告 设计题目 构造可以使设计题目 构造可以使 n n 个城市连接的最小生成个城市连接的最小生成 树树 姓名 姓名 学号 学号 专业 物联网工程 嵌入式培养 专业 物联网工程 嵌入式培养 院系 计算机技术与科学学院院系 计算机技术与科学学院 班级 班级 14051405 指导教师 指导教师 20162016 年年 0101 月月 0909 日日 第 1 页 共 17 页 摘要 本次课程设计的要求是给定一个地区的本次课程设计的要求是给定一个地区的 n n 个城市间的距离个城市间的距离 网 用网 用 PrimPrim 算法建立最小生成树 并计算得到的最小生成算法建立最小生成树 并计算得到的最小生成 树的代价 将该地区的城市用顶点表示 城市间的公路用树的代价 将该地区的城市用顶点表示 城市间的公路用 边表示 公路的长度作为边的权值 最终这个问题可以归边表示 公路的长度作为边的权值 最终这个问题可以归 结为网图中 求顶点结为网图中 求顶点 A A 到顶点到顶点 B B 的所有路径中 边的权值的所有路径中 边的权值 之和最少的那条路径 之和最少的那条路径 关键词 关键词 最小生成树最小生成树 PrimPrim 算法算法 C C 语言源程序语言源程序 第 2 页 共 17 页 Abstract TheThe currcurriculumiculum designdesign requirementsrequirements isis givengiven a a regionregion n n city city thethe distancedistance betweenbetween thethe netnet withwith thethe PrimPrim algorithmalgorithm toto establishestablish minimumminimum spanningspanning tree tree andand calculatedcalculated thethe priceprice ofof minimumminimum spanningspanning tree tree CitiesCities inin thethe regionregion withwith vertexvertex said said betweenbetween highwayhighway inin thethe citycity edge edge saidsaid thethe lengthlength ofof thethe roadroad asas thethe edgeedge ofof thethe rightright values values finallyfinally thethe problemproblem cancan bebe summedsummed upup inin networknetwork diagram diagram andand allall thethe pathspaths ofof vertexvertex A A toto B B thethe edgeedge ofof thethe weightsweights ofof thethe sumsum ofof thethe minimumminimum path path Keywords Keywords minimumminimum spanningspanning treetree PrimPrim algorithmalgorithm C C languagelanguage sourcesource programprogram 第 3 页 共 17 页 目 录 一 问题描述一 问题描述 4 1 1 题目内容题目内容 4 1 2 基本要求基本要求 4 二 需求分析二 需求分析 4 三 概要设计三 概要设计 4 3 1 邻接矩阵的建立邻接矩阵的建立 5 3 2 图的建立图的建立 5 3 3 求最小生成树求最小生成树 6 四 数据结构设计四 数据结构设计 7 五 算法设计五 算法设计 8 5 1 算法分析算法分析 8 5 2 算法实现算法实现 8 六 程序测试与实现六 程序测试与实现 9 6 1 主程序主程序 9 6 2 测试结果测试结果 10 七 调试分析七 调试分析 10 八 遇到的问题及解决办法八 遇到的问题及解决办法 10 九 心得体会九 心得体会 10 十 附录十 附录 11 第 4 页 共 17 页 一 一 问题描述问题描述 1 题目内容 给定一个地区的 n 个城市间的距离网 用 Prim 算 法建立最小生成树 并计算得到的最小生成树的代价 2 基本要求 a 城市间的距离网采用邻接矩阵表示 若两个城市之间不存 在道路 则将相应边的权值设为自己定义的无穷大值 要 求至少 10 个城市 15 条边 b 最小生成树中包括的边及其权值 并显示得到的最小生成 树的代价 二 二 需求分析需求分析 本程序的功能包括图的建立 采用邻接矩阵存储 和求最小生成树 1 图的建立涉及到顶点数组 data n 和邻接矩阵 Edge n n 顶点 数组运用顺序表完成 操作有 顶点的插入即顺序表的插入 邻接 矩阵的建立 操作有 插入弧和对应的权值 输出邻接矩阵 2 最小生成树是通过 Prim 算法完成的 Prim 里涉及到候选最 短边集 用数组 shortEdge n 表示候选最短边集 数组元素包括候选 最短边的的邻接点 adjvex 和权值 lowcost 两个域 三 三 概要设计概要设计 第 5 页 共 17 页 1 邻接矩阵的建立邻接矩阵的建立 1 邻接矩阵的初始化 顶点自己对自己的权值为 0 其余的 权值均为 MaxWeight 自定义的无穷大 999 AdjMatGraph AdjMatGraph const int sz sz 是顶点数 有参构造函数 for int i 0 i sz i for int j 0 j sz j if i j Edge i j 0 else Edge i j MaxWeight 无穷大 numOfEdges 0 2 邻接矩阵中点与点之间有弧的 则将两个顶点之间的权值 设为 weight 取代 MaxWeight 无穷大 999 void AdjMatGraph InsertEdge const int v1 const int v2 int weight 插入弧 权为 weight if v1Vertices ListSize v2Vertices ListSize cout 参数 v1 v2 有误 2 endl exit 0 Edge v1 v2 weight Edge v2 v1 weight numOfEdges 2 图的建立图的建立 struct RowColWeight 边信息三元组 int row int col int weight void AdjMatCreateGraph AdjMatGraph for i 0 i n i G InsertVertex V i 填充顶点信息 for i 0 i e i G InsertEdge E i row E i col E i weight 3 求最小生成树求最小生成树 struct shortEdge int lowcost int adjvex void AdjMatGraph Prim int k w cost 0 for int i 1 inumOfVertices i shortEdge i lowcost Edge 0 i shortEdge i adjvex 0 shortEdge 0 lowcost 0 for int i 1 inumOfVertices i w MaxWeight for int j 1 jnumOfVertices j if shortEdge j lowcost 0 k j shortEdge k lowcost 0 for int j 1 jnumOfVertices j if Edge k j shortEdge j lowcost shortEdge j lowcost Edge k j shortEdge j adjvex k 第 7 页 共 17 页 cout 最小生成树为 endl for int i 1 inumOfVertices i cout i shortEdge i adjvex Edge i shortEdge i adjvex endl cost cost Edge i shortEdge i adjvex cout 最小生成树代价为 cost endl 四 数据结构设计数据结构设计 元素类型 结点类型 class SeqList private DataType data MaxListSize int size public SeqList int ListSize const 返回元素的个数 size void Insert const DataType 在位置 pos 插入元素 item struct RowColWeight 边信息三元组 int row int col int weight struct RowColWeight 边信息三元组 int row int col int weight class AdjMatGraph private SeqList Vertices 用顺序表存储结点信息 int Edge MaxVertices MaxVertices 用数组存储带权或不带权的边 int numOfEdges 边数 shortEdge shortEdge MaxSize public AdjMatGraph const int sz MaxVertices 有参构造函数 sz 为顶点数 第 8 页 共 17 页 int numOfVertices 返回结点数目 return Vertices ListSize int numOfEdge 返回边数 return numOfEdges void InsertVertex const VerT 插入结点 vertex void InsertEdge const int v1 const int v2 int weight 插入弧 权为 weight void printMGraph void Prim 五 五 算法设计算法设计 1 算法分析算法分析 根据用 Prim 算法求最小生成树 设 G V E 是具有 n 个顶点的连通 网 T U TE 是 G 的最小生成树 T 的初始状态为 U u0 u0 V TE 重复执行下述操作 在所有 u U v V U 的边中找一条代价 最小的边 u v 并入集合 TE 同时 v 并入 U 直至 U V0 最后计算 得到的最小生成树的代价 2 算法实现算法实现 void AdjMatGraph Prim int k w cost 0 for int i 1 inumOfVertices i shortEdge i lowcost Edge 0 i shortEdge i adjvex 0 shortEdge 0 lowcost 0 for int i 1 inumOfVertices i w MaxWeight for int j 1 jnumOfVertices j 第 9 页 共 17 页 if shortEdge j lowcost 0 k j shortEdge k lowcost 0 for int j 1 jnumOfVertices j if Edge k j shortEdge j lowcost shortEdge j lowcost Edge k j shortEdge j adjvex k cout 最小生成树为 最小生成树为 endl for int i 1 inumOfVertices i cout i shortEdge i adjvex Edge i shortEdge i adjvex endl cost cost Edge i shortEdge i adjvex cout 最小生成树代价为 最小生成树代价为 cost endl 六 六 程序测试与实现程序测试与实现 1 主程序主程序 void main AdjMatGraph g char a A B C D E F G H I J RowColWeight rcw 0 4 1 0 1 2 4 5 3 0 5 4 1 5 5 5 6 6 1 2 7 2 6 8 2 7 9 2 3 10 3 7 11 3 9 12 8 9 13 7 8 14 6 7 15 int n 10 e 15 10 个顶点 个顶点 15 条边条边 AdjMatCreateGraph g a n rcw e cout 当前的顶点个数为 当前的顶点个数为 g numOfVertices endl cout 当前的边的条数为 当前的边的条数为 g numOfEdge endl g printMGraph g Prim 2 测试结果 测试结果 999 是我自己设置的无穷大 是我自己设置的无穷大 第 10 页 共 17 页 七 调试分析调试分析 1 图的邻接矩阵是一个 n n 的矩阵 所以其空间代价是 O n2 2 在求解最小生成树的过程中 会不断的读取任意两个顶点之 间边的权值 所以采用邻接矩阵 八 遇到的问题及解决办法遇到的问题及解决办法 在求解利用 Prim 求解最小生成树的过程中 算法能够看懂 但 是利用 C 程序去实现 还是有问题的 最后反复看代码 构造了 一个最短候选边集 即数组 shortEdge n 九 九 心得体会心得体会 第 11 页 共 17 页 本次课程设计用到了顺序表的建立与插入 图的邻接矩阵存储 最本次课程设计用到了顺序表的建立与插入 图的邻接矩阵存储 最 终实现了求终实现了求 n 个个城市城市之间的相同公路之间的最短距离 我主要学到之间的相同公路之间的最短距离 我主要学到 了将实际问题转换为自己所学到的知识 做到了学以致用 了将实际问题转换为自己所学到的知识 做到了学以致用 十 十 附录 源代码 附录 源代码 SeqList h include using namespace std class SeqList private DataType data MaxListSize int size public SeqList int ListSize const 返回元素的个数返回元素的个数 size void Insert const DataType 在位置在位置 pos 插入元素插入元素 item SeqList SeqList size 0 int SeqList ListSize const return size void SeqList Insert const DataType if size MaxListSize cout 顺序表已满无法插入 顺序表已满无法插入 endl exit 1 if possize 当当 pos 等于等于 size 时表示插入在最后时表示插入在最后 cout 参数参数 pos 越界出错越界出错 pos i data i data i 1 data pos item 在在 pos 位置插入位置插入 item size 数据元素个数数据元素个数 size 加加 1 AdjMatGraphLib h struct RowColWeight 边信息三元组边信息三元组 int row int col int weight void AdjMatCreateGraph AdjMatGraph for i 0 i n i G InsertVertex V i 填充顶点信息填充顶点信息 for i 0 i e i G InsertEdge E i row E i col E i weight AdjMatGraph h include const int MaxSize 100 struct shortEdge int lowcost int adjvex class AdjMatGraph private SeqList Vertices 用顺序表存储结点信息用顺序表存储结点信息 int Edge MaxVertices MaxVertices 用数组存储带权或不带权的边用数组存储带权或不带权的边 int numOfEdges 边数边数 shortEdge shortEdge MaxSize public AdjMatGraph const int sz MaxVertices 有参构造函数有参构造函数 sz 为顶点数为顶点数 int numOfVertices 返回结点数目返回结点数目 return Vertices ListSize 第 13 页 共 17 页 int numOfEdge 返回边数返回边数 return numOfEdges void InsertVertex const VerT 插入结点插入结点 vertex void InsertEdge const int v1 const int v2 int weight 插入弧插入弧 权为 权为 weight void printMGraph void Prim AdjMatGraph AdjMatGraph const int sz sz 是顶点数 有参构造函数是顶点数 有参构造函数 for int i 0 i sz i for int j 0 j sz j if i j Edge i j 0 else Edge i j MaxWeight 无穷大无穷大 numOfEdges 0 void AdjMatGraph InsertVertex const VerT void AdjMatGraph InsertEdge const int v1 const int v2 int weight 插入弧插入弧 权为权为 weight if v1Vertices ListSize v2Vertices ListSize cout 参数参数 v1 v2 有误有误 2 endl exit 0 Edge v1 v2 weight Edge v2 v1 weight numOfEdges void AdjMatGraph printMGraph cout 邻接矩阵是 邻接矩阵是 endl for int i 0 inumOfVertices i 第 14 页 共 17 页 for int j 0 jnumOfVertices j cout setw 10 Edge i j cout endl cout endl void AdjMatGraph Prim int k w cost 0 for int i 1 inumOfVertices i shortEdge i lowcost Edge 0 i shortEdge i adjvex 0 shortEdge 0 lowcost 0 for int i 1 inumOfVertices i w MaxWeight for int j 1 jnumOfVertices j if shortEdge j lowcost 0 k j shor