专业课程设计图的遍历

1、专业课程设计图的遍历目录一、课题的主要功能31.1 设计内容31.2 对课程设计功能的需求分析.3二、课题的功能模块的划分32.1 模块划分32.2 系统的概要设计4三、主要功能的实现53.1 算法思想51. 图的邻接矩阵的建立52. 图的遍历的实现53.2 数据结构53.3 主函数流程图63.4 深度优先遍历流程图 .73.5 深度优先遍历递归93.6 深度优先遍历流程图 .103.7 广度优先遍历递归流程图.12四、程序调试134.1 程序的调试分析134.2 程序的测试结果14五、总结 .18六、附件 .186.1 源程序182一、课题的主要功能1.1 设计内容演示图的深度优先 ,广度优

2、先遍历过程， 并输出原图结构及遍历结果。要求图的结点数不能少于 6 个。可以由系统随机生成图， 也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.2 对课程设计功能的需求分析图的遍历并不需要是一个过于复杂的工作环境，一般来说：最合适的才是最好的。软件设计必须符合我们使用实际情况的需要。根据要求，图的遍历主要功能如下：1.用户可以随时建立一个有向图或无向图；2.用户可以根据自己的需要，对图进行深度遍历或广度遍历；3.用户可以根据自己的需要对图进行修改；4. 在整个程序中 , 用户可以不断的按照不同的方式对图进行遍历 , 若不继续 , 用户也可以

3、随时跳出程序 , 同时 , 如果用户输入的序号错误 , 程序会提示用户重新输入序号；二、课题的功能模块的划分2.1 模块划分1. 队列的初始化、进队、出队、队列空、队列满的函数void InitQueue(CirQueue *Q) /初始化队列int QueueEmpty(CirQueue *Q)/队列是否为空int QueueFull(CirQueue *Q)/队列满Void EnQueue(CirQueue *Q,int x)/ 将队员进队 int DeQueue(CirQueue *Q)/ 将队员出队2. 创建图的函数void CreateMGraph(MGraph *G)/根据用户需要

4、创建一个图3. 图的深度优先遍历递归void DFSM(MGraph *G,int i)/*含有输出已访问的顶点的语句*/34. 图的广度优先遍历递归void BFSM(MGraph *G,int k) /*含有输出已访问的顶点的语句*/5. 深度优先遍历void DFSTraverseM(MGraph *G)/* 调用 DFSM函数 */6. 广度优先遍历void BFSTraverseM(MGraph *G) /*调用 BFSM函数 */7. 主函数main() /* 包含一些调用和控制语句 */2.2 系统的概要设计开始信息录入菜单选择深修广度改度优信优先息先退出程序4三、主要功能的实现

5、3.1 算法思想本课题所采用的是邻接矩阵的方式存储图，实现图的深度、广度两种遍历，并将每种遍历结果输出来。1.图的邻接矩阵的建立对任意给定的图（顶点数和边数自定），根据邻接矩阵的存储结构建立图的邻接距阵。2.图的遍历的实现图的遍历包括图的广度优先遍历与深度优先遍历。 对于广度优先遍历应利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）来实现。首先建立一空队列，从初始点出发进行访问，当被访问时入队，访问完出队。并以队列是否为空作为循环控制条件。 对于深度优先遍历则采用递归或非递归算法来实现，这里我所采用的是递归算法。3.2 数据结构#define Max 10#define FALSE 0#define TRUE 1#define Error printf#define QueueSize 30typedef structchar vexsMax;int edgesMaxMax;int n,e;5MGraph;int visitedMax;