普里姆算法生成最小生成树课程设计.doc

数据结构 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 数据结构分析数据结构分析 10 3 1 存储结构 10 3 2 算法描述 12 4 4 调试与分析调试与分析 22 4 1 调试过程 22 4 2 程序执行过程 22 参考文献参考文献 28 附附 录录 28 1 1 课程设计介绍课程设计介绍 1 11 1 课程设计内容课程设计内容 编写算法能够建立带权图 并能够用 Prim 算法求该图的最小 生成树 最小生成树能够选择图上的任意一点做根结点 最小生 成树输出采用顶点集合和边的集合的形式 1 21 2 课程设计要求课程设计要求 1 可以输入顶点 边数及各路径的权值 2 通过建立无向图或有向图能过输出邻接矩阵或邻接表 3 可以输出建立的最小生成树 4 画出流程图 且函数有必要说明 注释 5 课设完成后上交报告及核心代码 2 2 课程设计原理课程设计原理 2 12 1 课设题目粗略分析课设题目粗略分析 根据课设题目要求 拟将整体程序分为两大模块 以下是两个模块 的大体分析 1 创建网图并确定网图的存储形式 通过对题目要求的具体分析 发现该题的主要操作是路径的输出 因此采用邻接表和邻接矩阵 起点 终点和权值 两种存储结构 方便以后的编程 2 Prim 算法 设置两个新的集合 U 和 T 其中 U 用于存放带权图 G 的最小生成树的结点的集合 T 用于存放带权图 G 的最小生成树边的权 值的集合 其思想是 令集合 U 的初值为 U u0 即假设构造最小生成 树时从结点 u0 开始 集合 T 的初值为 T 从所有结点 u 属于 U 和 结点 v 属于 V 但不属于 U 的带权边中选出具有最小权值的边 u v 将结点 v 加入集合 U 中 将边 u v 加入集合 T 中 如此不断重复 当 U V 时 最小生成树便构造完毕 2 22 2 原理图介绍原理图介绍 2 2 12 2 1 功能模块图功能模块图 图 2 1 功能模块图 2 2 2 流程图分析流程图分析 1 主函数 显示菜单进行选择 选择创建 有 无向 图及存储方式 有向图邻接矩阵 无向图邻接矩阵 有向图邻接表 无向图邻接表 调用普里姆算法输出最小生成树 结束 开始 图 2 2 主函数流程图 2 CreateMGraph 函数 开始开始 显示菜单 选 择输入 1 或 2 选择 1选择 2 调用 createAgraph 函数 结束结束 选择 1 调用 CreateGraph 函 数 选择 2 调用 CreateMGraph 函数 调用 createALgraph 函数 调用 Prim 函数 输出 最小生成树 图 2 3 CreateMGraph 函数流程图 开始开始 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 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 结束结束 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 mincost max j 1 k 1 j n lowcost j mincost k j j N N printf 顶点的序号 d 边的权值 d n k mincost lowcost k 0 图 2 4 Prim 函数流程图 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 i firstedges s 5 邻接矩阵 Output 输出函数 图 2 6 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 结束结束 3 数据结构分析数据结构分析 3 13 1 存储结构存储结构 定义邻接矩阵及邻接表的结构体 1 邻接矩阵 define MaxVertexNum 100 define max 1000 typedef int VertexType typedef 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 int weight struct node next edgenode typedef struct vnode vertextype vertex edgenode firstedges 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 邻接表转换成邻接矩阵辅助结构体 3 23 2 算法描述算法描述 1 创建有向网图邻接矩阵存储 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 printf 输出顶点信息及邻接矩阵 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 初始化邻接矩阵 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 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 DispAdjList g 4 创建无向网图邻接表存储 void createALgraph ALgraph g 创建无向网图 int i j k w edgenode s printf t 无向网图邻接表 n 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 edgenode s adjvex i s weight w s next g adjlist j firstedges g adjlist j firstedges s 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 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 6 输出邻接矩阵存储函数 void OutPut MGraph G int i j printf tE for i 0 in i printf d G vexs i printf printf n for i 0 in i for j 0 jn j printf t d G edges i j printf n 7 输出邻接表存储函数 void DispAdjList ALgraph g int i edgenode p printf n 网图的邻接表表示如下 n for i 0 in i printf d 3d i g adjlist i vertex p g adjlist i firstedges while p NULL printf d d p adjvex p weight p p next printf n 8 邻接表转换成邻接矩阵函数 void change ALgraph g 邻接表转换成邻接矩阵 int i j edgenode p graph M M graph malloc sizeof graph M n g n M e g e for i 0 ie i for j 0 je j if i j M edges i j 0 else M edges i j MaxVertexNum for i 0 in i M vexs i g adjlist i vertex for i 0 in i p g adjlist i firstedges while p M edges i p adjvex p weight p p next prim M edges M n M vexs 4 4 调试与分析调试与分析 4 14 1 调试过程调试过程 测试数据 对下图进行测试 4 2 程序执行过程程序执行过程 系统使用说明 1 输入的数据可以是 100 以内的整数 2 本系统可以建立带权图 并能够用 Prim 算法求该网图的最小生 成树 3 该系统会有菜单提示 进行选项 右图是 6 个顶点的 10 条边的 连通图 六个顶点分别是 1 2 3 4 5 6 顶点序号和边上的权植分别是 0 1 11 0 2 15 0 3 18 1 2 33 1 4 12 2 3 20 2 4 22 2 5 25 3 5 27 4 5 29 1 24 3 5 6 4 程序实际运行截图 1 有向图邻接矩阵输出最小生成树截图 2 无向图邻接矩阵输出最小生成树截图 3 有向图邻接表输出最小生成树截图 4 无向图邻接表输出最小生成树截图 参考文献参考文献 1 李素若 数据结构 C 语言描述 2009 化学工业出版社 2 严蔚敏 吴伟民 数据结构 C 语言描述 1999 清华大学出 版社 3 徐孝凯 数据结构课程实验 2002 清华大学出版社 4 孟佳娜 胡潇琨 算法与数据结构实验与习题