《《普里姆算法生成最小生成树课程设计》-毕业论文·公开DOC》由会员分享，可在线阅读，更多相关《《普里姆算法生成最小生成树课程设计》-毕业论文·公开DOC（31页珍藏版）》请在金锄头文库上搜索。
1、 数据结构 C 语言描述 课程设计 学 院 计算机工程学院 班 级 12 级软件技术 1 班 学 号 2012304040122 120 124 133 121 学生姓名 周鑫 王彬彬 李松平 张圣玮 魏远迎 指导教师 余云霞 2014年 1月 3 日 JINGCHU UNIVERSITY OF TECHNOLOGY 目目 录录 1 1 课程设计介绍课程设计介绍 1 1 1 课程设计内容 1 1 2 课程设计要求 1 2 2 课程设计原理课程设计原理 2 2 1 课设题目粗略分析 2 2 2 原理图介绍 3 2 2 1 功能模块图 3 2 2 2 流程图分析 3 3 数据结构分析数据结构分析
2、10 3 1 存储结构 10 3 2 算法描述 12 4 4 调试与分析调试与分析 22 4 1 调试过程 22 4 2 程序执行过程 22 参考文献参考文献 28 附附 录录 28 第 0 页 共 29 页 1 1 课程设计介绍课程设计介绍 1 11 1 课程设计内容课程设计内容 编写算法能够建立带权图 并能够用 Prim 算法求该图的最小 生成树 最小生成树能够选择图上的任意一点做根结点 最小生 成树输出采用顶点集合和边的集合的形式 1 21 2 课程设计要求课程设计要求 1 可以输入顶点 边数及各路径的权值 2 通过建立无向图或有向图能过输出邻接矩阵或邻接表 3 可以输出建立的最小生成树
3、 4 画出流程图 且函数有必要说明 注释 5 课设完成后上交报告及核心代码 第 1 页 共 29 页 2 2 课程设计原理课程设计原理 2 12 1 课设题目粗略分析课设题目粗略分析 根据课设题目要求 拟将整体程序分为两大模块 以下是两个模块 的大体分析 1 创建网图并确定网图的存储形式 通过对题目要求的具体分析 发现该题的主要操作是路径的输出 因此采用邻接表和邻接矩阵 起点 终点和权值 两种存储结构 方便以后的编程 2 Prim 算法 设置两个新的集合 U 和 T 其中 U 用于存放带权图 G 的最小生成树的结点的集合 T 用于存放带权图 G 的最小生成树边的权 值的集合 其思想是 令集合
4、U 的初值为 U u0 即假设构造最小生成 树时从结点 u0 开始 集合 T 的初值为 T 从所有结点 u 属于 U 和 结点 v 属于 V 但不属于 U 的带权边中选出具有最小权值的边 u v 将结点 v 加入集合 U 中 将边 u v 加入集合 T 中 如此不断重复 当 U V 时 最小生成树便构造完毕 第 2 页 共 29 页 2 22 2 原理图介绍原理图介绍 2 2 12 2 1 功能模块图功能模块图 显示菜单进行选择 选择创建 有 无向 图及存储方式 有向图邻接矩阵 无向图邻接矩阵 有向图邻接表 无向图邻接表 调用普里姆算法输出最小生成树 结束 开始 图 2 1 功能模块图 2 2
5、 2 流程图分析流程图分析 1 主函数 第 3 页 共 29 页 开始开始 显示菜单 选 择输入 1 或 2 选择 1选择 2 调用 createAgraph 函数 结束结束 选择 1 调用 CreateGraph 函 数 选择 2 调用 CreateMGraph 函数 调用 createALgraph 函数 调用 Prim 函数 输出 最小生成树 图 2 2 主函数流程图 2 CreateMGraph 函数 第 4 页 共 29 页 开始开始 int i j k for i 0 in i scanf n c for i 0 in i for j 0 in i i j G edges i j
6、0 YN G edges i j max for k 0 ke k scanf n d d d G edges i j weight OutPut G prim G edges G n G vexs 图 2 3 CreateMGraph 函数流程图 结束结束 第 5 页 共 29 页 3 Prim 函数 开始开始 int i j k lowcost 100 mincost for i 1 i n i lowcost i gm 0 i closevertex i 0 set i 0 i 1 j 1 Y Y lowcost 0 0 closevertex 0 0 for i 1 i n i min
7、cost max j 1 k 1 j n lowcost j mincost k j j N N printf 顶点的序号 d 边的权值 d n k mincost lowcost k 0 第 6 页 共 29 页 for j 0 j n j gm k j n for i 0 in i scanf d g adjlist i firstedges NULL for k 0 ke k scanf d d d s edgenode malloc sizeof edgenode s adjvex j s weight w s next g adjlist i firstedges g adjlist
8、 i firstedges s 第 8 页 共 29 页 5 邻接矩阵 Output 输出函数 开始开始 int i j for i 0 in i printf d G vexs i for i 0 in i for j 0 jn j printf t d G edges i j 结束结束 图 2 6 Output 函数流程图 第 9 页 共 29 页 3 数据结构分析数据结构分析 3 13 1 存储结构存储结构 定义邻接矩阵及邻接表的结构体 1 邻接矩阵 define MaxVertexNum 100 define max 1000 typedef int VertexType typede
9、f int EdgeType typedef struct VertexType vexs MaxVertexNum EdgeType edges MaxVertexNum MaxVertexNum int n e MGraph 2 邻接表 define MaxVertexNum 100 typedef int vertextype typedef struct node int adjvex 第 10 页 共 29 页 int weight struct node next edgenode typedef struct vnode vertextype vertex edgenode fi
10、rstedges vertexnode typedef vertexnode AdjList MaxVertexNum typedef struct AdjList adjlist int n e ALgraph 3 邻接表转换成邻接矩阵辅助结构体 typedef int edgetype typedef struct edgetype vexs MaxVertexNum edgetype edges MaxVertexNum MaxVertexNum int n e graph 邻接表转换成邻接矩阵辅助结构体 第 11 页 共 29 页 3 23 2 算法描述算法描述 1 创建有向网图邻接矩
11、阵存储 void CreateMGraph MGraph G int i j k weight printf t 有向网图邻接矩阵 n printf 请输入顶点数和边数 scanf d d printf 请输入顶点信息 for i 0 in i scanf n d for i 0 in i for j 0 jn j if i j G edges i j 0 else G edges i j max 初始化邻接矩阵 printf 输入边对应的两个顶点的序号及权值 for k 0 ke k scanf n d d d G edges i j weight 第 12 页 共 29 页 printf
12、输出顶点信息及邻接矩阵 n OutPut G printf 输出最小生成树的信息 n prim G edges G n G vexs 2 创建无向网图邻接矩阵存储 void CreateGraph MGraph G int i j k weight printf t 无向网图邻接矩阵 n printf 请输入顶点数和边数 scanf d d printf 请输入顶点信息 for i 0 in i scanf n d for i 0 in i for j 0 jn j if i j G edges i j 0 else G edges i j max 初始化邻接矩阵 第 13 页 共 29 页
13、printf 输入边对应的两个顶点的序号及权值 for k 0 ke k scanf n d d d G edges i j weight G edges j i weight printf 输出顶点信息及邻接矩阵 n OutPut G printf 输出最小生成树的信息 n prim G edges G n G vexs 3 创建有向网图邻接表存储 void createAgraph ALgraph g 创建有向网图 int i j k w edgenode s printf t 有向网图邻接表 n printf 输入顶点数和边数 scanf d d c printf n 输入顶点 for
14、i 0 in i 第 14 页 共 29 页 scanf d g adjlist i firstedges NULL printf n 输入边和权值 for k 0 ke k scanf d d d s edgenode malloc sizeof edgenode s adjvex j s weight w s next g adjlist i firstedges g adjlist i firstedges s DispAdjList g 4 创建无向网图邻接表存储 void createALgraph ALgraph g 创建无向网图 int i j k w edgenode s pr
15、intf t 无向网图邻接表 n 第 15 页 共 29 页 printf 输入顶点数和边数 scanf d d c printf n 输入顶点 for i 0 in i scanf d g adjlist i firstedges NULL printf n 输入边和权值 for k 0 ke k scanf d d d s edgenode malloc sizeof edgenode s adjvex j s weight w s next g adjlist i firstedges g adjlist i firstedges s s edgenode malloc sizeof e
16、dgenode s adjvex i s weight w s next g adjlist j firstedges g adjlist j firstedges s 第 16 页 共 29 页 DispAdjList g 5 prim 算法 void prim int gm MaxVertexNum int n int closevertex 普里姆算法 int lowcost 100 int mincost int i j k for i 0 i n i lowcost i gm 0 i closevertex i 0 lowcost 0 0 closevertex 0 0 for i 1 i n i mincost max j 1 第 17 页 共 29 页 k 1 while j n if lowcost j mincost k j j printf 顶点的序号 d 边的权值 d n k mincost lowcost k 0 for j 0 j n j if gm k j lowcost j lowcost j gm k j closevertex j k 第 18 页 共
