数据结构课程设计（论文）：基于邻接矩阵的图的遍历

《数据结构课程设计（论文）：基于邻接矩阵的图的遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、武汉理工大学《数据结构》课程设计说明书目录1引言…………………………………………………………………………22需求分析……………………………………………………………………32.1设计目的……………………………………………………………32.2设计任务……………………………………………………………32.3基本操作……………………………………………………………32.3.1程序调用的基本函数………………………………………32.3.2各函数的调用关系…………………………………………43数据结构设计………………………………………………………………43.1队列……………………………………………

2、……………………43.1.1队列的类型定义………………………………………………43.1.2循环队列的存储结构…………………………………………53.2基于邻接矩阵的图(MGraph)……………………………………53.2.1图的类型定义………………………………………………53.2.2图的结构……………………………………………………54算法设计……………………………………………………………………54.1邻接矩阵的建立与输出…………………………………………54.1.1建立基于邻接矩阵的无向图中………………………………54.1.2邻接矩阵方式输出无向图……………………………………74.2

3、遍历搜索算法设计…………………………………………………74.2.1深度优先搜索…………………………………………………74.2.2广度优先搜索…………………………………………………85程序实现及测试……………………………………………………………95.1程序测试数据………………………………………………………95.2调试过程及分析…………………………………………………96设计体会……………………………………………………………………106.1不足之处……………………………………………………………106.2课程设计感悟………………………………………………………10结束语………………………

4、…………………………………………………11参考文献………………………………………………………………………11附件：源程序……………………………………………………………………12程序运行结果……………………………………………………………1919武汉理工大学《数据结构》课程设计说明书基于邻接矩阵的图的遍历摘要:本课程设计主要目的在于更深一步的了解图的遍历的问题输入的图转换为邻接矩阵存储，并基于邻接矩阵实现图的深度优先遍历(DFS)和广度优先遍历(BFS)。实验证明，两种算法的遍历结果截然不同，但均能完成对图的遍历过程。在课程设计中，程序设计设计语言运行环境为VisualC++，程序

5、运行平台为windowsXP。summary:Themainpurposeofthiscoursedesignistounderstandgraphtraversalproblemsfurtherandweshouldlearnhowtochangetheinputdiagramintoadjacencymatrixstorage,andrealizegraphdepth-firsttraversal(DFS)andbreadth-firsttraversal(BFS),basedontheadjacencymatrix.Theexperimentalresultsprovet

6、hattheresultsofthetwoalgorithm'sergodicarequitedifferent,butallcancompletethegraphtraversalprocess.Inthecurriculumdesign,programdesignlanguageisrunningintheenvironmentofVisualc++.ProgramoperationplatformisWindowsXP.关键字：图、存储结构、邻接矩阵、遍历。Keywords:Diagram、storagestructure、adjacencymatrix、ergodic.

7、1引言图论在现代计算机科学中占有举足轻重的地位，而许多的图论问题需要在图中遍历来寻找某个特定的结构，图的遍历算法从而变得十分重要。图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的两种算法即广度优选遍历和深度优选遍历的实现。从图的定义可知，一个图的信息包括两个部分，即图中的顶点信息及描述图的顶点间的关系——边或者弧的信息。因此，无论采用