资源描述：
《数据结构与算法课程设计报告---图的算法实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、数据结构与算法课程设计报告课程设计题目：图的算法实现专业班级：信息与计算科学1002班目录摘要…………………………………………………11、引言……………………………………………12、需求分析………………………………………13、概要设计………………………………………24、详细设计………………………………………45、程序设计………………………………………106、运行结果………………………………………187、总结体会………………………………………19摘要(题目):图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、
2、Kruskal、Dijkstra和拓扑排序算法。关键字:邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法等问题。通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。（1）通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v
3、)，将其顶点加入到生成树的顶点集合V中。以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。拓扑排序算法思想： 1、从有向图中选取一个没有前驱的顶点，并输出之； 2、从有向图中删去此顶点以及所有以它为尾的弧； 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱--入度为零，删除顶点及以它为尾的弧--弧头顶点的入度减1。2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：（1）用邻
4、接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；（2）用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；（3）用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；（4）实现该图的拓扑排序算法。3.概要设计ADTGraph{数据对象V:V是具有相同特性的数据元素的集合，称为顶点集；数据关系R：R={VR}VR={
5、v,w∈V且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息}基本操作：CreateGraph(&G,V,VR);StatusCreateGrap
6、h(MGraph&G)//采用邻接矩阵表示法，构造图G.StatusCreateGraph(MGraph&G)//采用邻接表表示法，构造图GStatusMinSpanTree_Prim(MGraphG,VertexTypeu)//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边StatusMinSpanTree_Kruskal(MGraphG,VertexTypeu)//用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边StatusShortestPath_DIJ(MGraphG,intv0,PathMatrix&p,ShortPathTable&D)/
7、/用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]StatusTopSort(ALGraphG)//若G中无回路，则输出G的顶点的一个拓扑排序并返回OK,否则返回ERROR存储结构typedefstruct//邻接矩阵存储结构{intno;intinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode//邻接表存储结构{intadjvex;structANode*nextarc;intinfo;}
8、ArcNode;typedefstructVnode{intdata;intcount;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct{AdjListadjlist;intn,e;}ALGraph;typedefstructnode{intdata;structnode*next;}List;4、详细设计图的邻接矩阵存储结构算法：
