天津理工大学数据结构实验报告4

《天津理工大学数据结构实验报告4》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验（四）实验名称图的深度优先与广度优先遍历软件环境　　　　Windows98/2000,VC++6.0或turboC硬件环境PⅡ以上微型计算机实验目的　　理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。实验内容（应包括实验题目、实验要求、实验任务等）图的遍历利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。实验过程与实验结果（可包括实

2、验实施的步骤、算法描述、流程、结论等）实验步骤及算法描述和流程：1.无向图的邻接矩阵存储结构1.1创建无向图的边的结构，由该边的信息指针和组成该边的两个顶点的位置以及指向与两个顶点相连的下一条边构成1.2创建无向图的顶点结构，由顶点所存储的信息和指向依附该顶点的边的指针构成1.3创建无向图的结构，由顶点结构数组和无向图当前的顶点数和边数构成1.4利用单链队列作为无向图的邻接表存储结构2.采用邻接表存储结构，构造无向图2.1输入无向图的相关信息：顶点数，边数，再输入顶点信息构造表节点链表2.2输入顶点间的关系，构造出无向图的邻接表3.深度优先遍历无向图3.1编写函数

3、DFS，从顶点v出发，对v所在的连通分量进行深度优先搜索，并利用递归，输出结点信息并对未访问的结点调用DFS函数3.2编写函数DFSTraverse对无向图做深度优先搜索，对已访问的结点标记，对尚未访问过得结点调用DFS4.广度优先遍历无向图使用辅助队列Q和访问标志数组visite对无向图进行非递归广度优先搜索4.1用for循环给顶点访问标志数组置初值04.2若顶点未访问4.2.1对要访问顶点访问标志置为1，顶点入队4.2.2循环当队列不为空时，队头元素出队赋给u，并将u的未访问的邻接点入队5.主函数5.1调用无向图创建函数从键盘输入数据创建无向图5.2调用深度优

4、先函数，输出无向图的深度优先搜索5.3调用广度优先函数，输出无向图的广度优先搜索结论：因为程序中邻接表的出入为头插法，所以对于输入无向图的关系时，邻接表的生成总与输入时的顺序相反，在做深度与广度优先搜索时，对于结点a，首先访问的结点，是输入边的关系时最后输入的附录（可包括源程序清单或其它说明）#include#include#defineMAX_NAME10#defineMAX_INFO80typedefcharInfoType;typedefcharVertexType[MAX_NAME];//字符串类型#defineMAX_V

5、ERTEX_NUM20typedefenum{unvisited,visited}VisitIf;typedefstructEBox{VisitIfmark;//访问标记intivex,jvex;//该边依附的两个顶点的位置structEBox*ilink,*jlink;//分别指向依附这两个顶点的下一条边InfoType*info;//该边信息指针}EBox;typedefstruct{VertexTypedata;EBox*firstedge;//指向第一条依附该顶点的边}VexBox;typedefstruct{VexBoxadjmulist[MAX_VER

6、TEX_NUM];intvexnum,edgenum;//无向图的当前顶点数和边数}AMLGraph;typedefintQElemType;typedefstructQNode{//单链表的链式存储结构QElemTypedata;//数据域structQNode*next;//指针域}QNode,*QueuePtr;typedefstruct{QueuePtrfront,//队头指针，指针域指向队头元素rear;//队尾指针，指向队尾元素}LinkQueue;//若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1intLocateVex(AMLGraph

7、G,VertexTypeu){inti;for(i=0;i

8、值(<%d