实现prim-kruskal-dijkstra和拓扑排序算法doc.doc

实现 Prim-Kruskal-Dijkstra 和拓扑排序算法 doc 自己收集整理的错误在所难免仅供参考交流如有错误请指正!谢谢福建农林大学计算机与信息学院计算机类课程设计报告课程名称: 数据结构课程设计题目: 图的算法实现(1 )将图的信息建立文件; 2 )从文件读入图的信息建立邻接矩阵和邻接表;(3) 实现 Prim 、 Kruskal 、 Dijkstra 和拓扑排序算法姓名: 易向阳系: 计算机专业: 计算机科学与技术(专升本) 年级: 07级学号: 071806019 指导教师: 黄思先职称: 副教授 2008 年 06月 28日目录 1 .课程设计的目的.......................................................... ........4 2 .课程设计要求.......................................................... ...........4 3 .算法思想描述.......................................................... ...........4 、存储结构的建立.......................................................... ..4 、 Prim 算法.......................................................... ...........4 、 Kruskal 算法.......................................................... ........5 、 Dijkstra 算法.......................................................... .....5 、拓扑排序算法.......................................................... .....5 4 .程序结构.......................................................... .................5 5 .测试结果.......................................................... .................6 6 .总结.......................................................... .......................7 参考文献.......................................................... .......................8 附录: ......................................................... ...........................9 1. 课程设计的目的此次课程设计的目的是以 C 语言为基础通过完成一些具有一定难度的课程设计题目的编写、调试、运行工作进一步了解并掌握数据结构与算法的设计方法具备初步的独立分析和设计能力;初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 巩固所学理论知识使理论与实际相结合从而提高自我分析问题、解决问题的能力用系统的观点和软件开发一般规范进行软件开发培养软件工作者所应具备的科学的工作方法和作风, 同时培养学生调查研究、查阅技术文献、资料、手册以及编写技术文献的能力 2. 课程设计要求图的算法实现(1 )将图的信息建立文件; (2 )从文件读入图的信息建立邻接矩阵和邻接表; (3 )实现 Prim 、 Kruskal 、 Dijkstra 和拓扑排序算法 3. 算法思想描述本程序涉及到图的存储结构的建立、 Prim 、 Kruskal 、 Dijkstr a 和拓扑排序算法 、存储结构的建立: 实现从文件中读入图的信息同时建立: 有向邻接矩阵、无向邻接矩阵、有向邻接表、无向邻接表首先进行有向邻接矩阵、邻接表和无向邻接矩阵、邻接表的初始化初始化有向邻接矩阵和无向邻接矩阵时因为不知道会读入几个顶点和几条边所以取无向邻接矩阵把它存顶点的字符数组各字符初始化为"*", 以方便判断顶点名称记录到哪了各边的度都初始化为 9999, 表示不连通. 顶点数和边数都初始为 0, GraphKind 分别初始为 YOUXIANG,WUXIANG