1、 数据结构与算法数据结构与算法 课程设计课程设计报告报告 课程设计课程设计题目：题目： 图的算法实现图的算法实现 专业班级：专业班级： 信息信息与计算科学与计算科学 10100 02 2 班班 目录目录 摘要摘要1 1 1 1、 引言引言1 1 2 2、 需求分析需求分析1 1 3 3、 概要设计概要设计2 2 4 4、 详细设计详细设计4 4 5 5、 程序设计程序设计1010 6 6、 运行结果运行结果1818 7 7、 总结体会总结体会1919 摘要摘要( (题目题目): ): 图的算法实现图的算法实现 实验内容实验内容 图的算法实现图的算法实现 问题描述：问题描述： （1）将图的信息建
2、立文件；）将图的信息建立文件； （2）从文件读入图的信息，建立邻接矩阵和邻接表；）从文件读入图的信息，建立邻接矩阵和邻接表； （3）实现）实现 Prim、Kruskal、Dijkstra 和拓扑排序算法。和拓扑排序算法。 关键字关键字: : 邻接矩阵、邻接矩阵、Dijkstra 和拓扑排序算法和拓扑排序算法 1.1.引言引言 本次数据结构课程设计共完成图的存储结构的建立、本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra 和拓扑排序算法等问题。通过本次课程设计，可以巩固和加深对数据结构的理和拓扑排序算法等问题。通过本次课程设计，可以巩固和加深对数据结构的理
3、 解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。 （1） 通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作； （2） 能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问 题的正确求解过程并编写代码实现。题的正确求解过程并编写代码实现。 使用语言：使用语言：C Prim算法思想：算法思想：从连通网从连通网 N=V,E中的某一顶点中的某一顶点 v0出发，选择与它关联的具有出发，选择与它关联的具有 最小权值的最小权值的边边(v0,v)，将其顶点加入到生成树的顶点集合，将其顶点加入到生成树的顶点集合 V中。以后每一步从一中。以后每一步从一 个顶点在个顶点在 V 中，而另一个顶点不在中，而另一个顶点不在 V中的各条边中选择权值最小的边中的各条边中选择权值最小的边(u,v),把
