图的遍历与最小生成树的实现

《图的遍历与最小生成树的实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数学与计算机学院课程设计说明书课程名称:数据结构-课程设计课程代码:题目:图的遍历与最小生成树年级/专业/班:学生姓名:学　　号:开始时间:2011年06月14日完成时间:2011年06月27日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月日摘要图是一种比线形表和树更为复杂的数据结构。在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储

2、。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。关键词：图；存储结构；遍历目录1需求分析31.1任务与要求31.2程序的主要功能31.2.1邻接矩阵存储结构31.2.2邻接链表存储结构41.2.3十字链表存储结构42开发及运行平台53概要设计53.1概要设计图53.2抽象数据的说明64详细设计85系统测试86结论15参考文献16附录171需求分析1.1任务与要求本程序设计的主要任务是为了完成以下功能：1.由键盘向程序输入相关数据；2.程序处

3、理输入数据，以十字链表，邻接矩阵和邻接链表的形式输出；3.根据已建成的图，程序实现图的深度优先遍历；4.程序输出图的广度优先遍历顺序；5.显示图的最小生成树，连同分量的实现；6.采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。测试数据：1.邻接矩阵测试数据：66abcdefab2ae6ad5bd4bc1bf32.邻接链表测试数据：78abcdefgabaeacafbgbddgcf3.十字链表测试数据：453225439934661.2程序的主要功能1.2.1邻接矩阵存储结构该模块主要可以实现用邻接

4、矩阵建图，使用不同方法遍历改图，实现最小生成树以及非连同图的连通分量的求解如图：图1.2.1邻接矩阵存储结构1.2.2邻接链表存储结构该模块主要实现：用邻接链表建图，使用不同方法遍历图，如下：图1.2.2邻接链表存储结构1.2.3十字链表存储结构该模块主要可以实现：创建十字链表，十字链表的显示，查找元素，如图:图1.2.3十字链表存储结构2开发及运行平台开发平台：Microsoftvisualstudio2008运行平台：Windows;3概要设计3.1概要设计图根据本系统对功能实现的要求，主要可以分为一下三个

5、大的模块：1.邻接矩阵存储结构；2.邻接链表存储结构；3.十字链表存储结构；其中每个模块又包涵其它相应的子功能模块。则根据以上可以得到本系统的概要设计图如下图示：图3.1概要设计图3.2抽象数据的说明本程序中相关抽象数据定义如下：#ifndefCOMMON_H#defineCOMMON_H#includeusingnamespacestd;constintMAX=10;//最大结点数boolvisited[MAX];//访问数组//-------邻接链表---------------type

6、defstructArcNode{intadjvex;ArcNode*next;}ArcNode;typedefstruct{chardata;ArcNode*firstarc;}AdjList[MAX];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;//----邻接矩阵----------------------------typedefstruct{charvertices[MAX];//结点向量intarcs[MAX][MAX];//邻接矩

7、阵intvexnum,arcnum;//结点数和弧数}MGraph;struct{charadjvex;intlowcost;}closedge[MAX];//----------十字链表-----------------------structlinknode{introws,cols;linknode*down,*right;unionvnext{intv;linknode*next;}node;};linknode*CreateMatlind();linknode*InputMatlind(linknod

8、e,int);voidShowMatlind(linknode);voidSearchMatlind(linknode*hm,ints);#endif4详细设计在以上工作的基础上，基本的设计已经完成。由此可以得出整个系统的层次图：图4.1主要层次图5系统测试登录系统主界面，如下图：图5.1系统主菜单选择功能1，进入第二菜单界面：图5.2邻接矩阵存储结构选择1，建立矩阵图：图5.3邻接矩