资源描述：
《图的遍历实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.实验四：图的遍历题目：图及其应用——图的遍历班级：姓名：学号：完成日期：一.需求分析1.问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。2.基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。3.测试数据：教科书图7.33。暂时忽略里程，起点为北京。4.实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每
2、个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。5.选作内容：（1）.借助于栈类型（自己定义和实现），用非递归算法实现深度优先遍历。（2）.以邻接表为存储结构，建立深度优先生成树和广度优先生成树，再按凹入表或树形打印生成树。二.概要设计1.为实现上述功能，需要有一个图的抽象数据类型。该抽象数据类型的定义为：ADTGraph{数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R={VR}VR={
3、v，wv且P(v，w)，表示从v到w得弧，谓词P(v，w)定义了弧的意义
4、或信息}}ADTGraph2.此抽象数据类型中的一些常量如下：#defineTRUE1#defineFALSE0#defineOK1#definemax_n20//最大顶点数typedefcharVertexType[20];typedefenum{DG,DN,AG,AN}GraphKind;enumBOOL{False,True};3.树的结构体类型如下所示：word范文.typedefstruct{//弧结点与矩阵的类型intadj;//VRType为弧的类型。图--0,1;网--权值int*Info;//与弧相关的信息的指针,可省略}ArcCell,A
5、djMatrix[max_n][max_n];typedefstruct{VertexTypevexs[max_n];//顶点AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//顶点数，边数}MGraph;//队列的类型定义typedefintQElemType;typedefstructQNode{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;4.本程序包含三个模块1).主程序模
6、块voidmain(){创建树；深度优先搜索遍历；广度优先搜索遍历；}2).树模块——实现树的抽象数据类型3).遍历模块——实现树的深度优先遍历和广度优先遍历各模块之间的调用关系如下：主程序模块树模块遍历模块word范文.三.详细设计#include"stdafx.h"#includeusingnamespacestd;#defineTRUE1#defineFALSE0#defineOK1#definemax_n20//最大顶点数typedefcharVertexType[20];typedefenum{DG,DN,AG,AN}Graph
7、Kind;enumBOOL{False,True};typedefstruct{//弧结点与矩阵的类型intadj;//VRType为弧的类型。图--0,1;网--权值int*Info;//与弧相关的信息的指针,可省略}ArcCell,AdjMatrix[max_n][max_n];typedefstruct{VertexTypevexs[max_n];//顶点AdjMatrixarcs;//邻接矩阵intvexnum,arcnum;//顶点数，边数}MGraph;//队列的类型定义typedefintQElemType;typedefstructQNode
8、{QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;//初始化队列intInitQueue(LinkQueue*Q){word范文.returnOK;}//判断队列是否为空intEmptyQueue(LinkQueueQ){if(Q.front==Q.rear)returnTRUE;elsereturnFALSE;}//入队列intEnQueue(LinkQueue*Q,QElemTypee){QueuePtr
9、p;p->data=e;p->next=NULL;(
