实验07图的存储与遍历

《实验07图的存储与遍历》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验7图的存储与遍历一、实验目的掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(dfs)和广度优先遍历(BFS)橾作的实现。二、实验内容内容1对以邻接矩阵为存储结构的图进行DFS和BFS遍历(1)问题描述：以邻接矩阵为图的存储结构，实现图的DFS和BFS遍历。(2)基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS和BFS序列。(3)测试数据：如图下图所示。要当前结点未访问过，就访问该结点，沿着其一条分支深入下去，每深入一个未访问过的结点，就访问这个结

2、点，然后从这个结点继续进行DFS遍历。在这一过程中，若深入时遇到一个已访问过的结点，则查找是否有与这个结点相邻的下一个未访问过的结点。若有则继续深人，否则将退回到这个结点的前一个结点，再找下一个相邻的本访问过的结点，……如此进行下去，直到所有的结点都被访问过。BFS遍历可利用队列来帮助实现，也可以用栈。实现方法与二叉树的层次遍历类似。题2对以邻接表为存储结构的阁进行DFS和BFS遍历(1)问题描述：以邻接表为存储结构，实现图的DFS和BFS遍历。(2)基本要求：建立一个图的邻接表存储，输出顶点的一种DFS

3、和BFS序列。(3)测试数据：如下阁所示:(1)实现提示：以邻接表为存储结构的图的DFS和BFS算法的实现思想与以邻接矩阵为存储结构的实现是一样的。只是由于图的存储形式不冋。而具体到取第一个邻接点和下一个邻接点的语句表示上有所差别而已。三、实验步骤1.明确图的ADT定义；2.在不同存储结构下定义顶点节点、边节点、图，以及创建、求邻接点、遍历等基本橾作的实现；3.利用图的基本橾作创建图；4.通过测试数据检验；5.提交实验报告。四、实现提示部分代码#defineMaxVertexNum10//设最大顶点数为1

4、0^include^includetypedefcharVertexType;typedefintEdgeType;typedefstruct{charvexs[10];intedges[10][10];intn,e;}MGraph;^defineFALSE0#defineTRUE1#defineErrorprintfintvisited[10];voidCreateMGraph(MGraph氺G);voidDFSTraverseM(MGraph*G);voidBFS

5、TraverseM(MGraph*G);voidDESM(MGraph*G,inti);voidBFSM(MGraph*G,inti);^defineQueueSize30A假定预分配的队列空间最多为30*/typedefintDataType;/*队列中的元素类型为字符型*/typcdcfstruct{intfront;/*队头指针，队非空时指向队头元素*/intrear;/*队尾指针，队非空时指向队尾元素的下一位罝*/intcount;A计数器，记录队中元素总数*/DataTypedata[Queue

6、Size];}CirQucuc;voidInitQueue(CirQueue*Q)/*初始队列*/{Q->front=Q->rear=0;Q->count=0;intQueueEmpty(CirQueue*Q)/*判队空*/{returnQ->count==0;}intQucucFull(CirQueue*Q)/*判队满*/{returnQ-〉count==QueueSize;}voidEnQueue(CirQueue*Q,DataTypex)A入队*/{if(QueueFull(Q))Error(，zQ

7、ueueoverflow");/*队满上溢*/else{Q-〉count++;/*队列元素个数加1*/Q-〉data[Q-〉rear]=x;/*新元素插入队列*/Q->rear=(Q->rear+l)%QueueSize;A循环队列的尾指针加1*/}}DataTypeDcQucuc(CirQueue*Q)/*出队*/{DataTypetemp;if(QueueEmpty(Q))Error("Queueunderflow");/*队空下溢*/else{temp=Q->data[Q->front];Q->co

8、unt—;A队列元素个数减1*/Q->front=(Q->front+l)%QueueSize;/*循环队列的头指针加1*/returntemp;}main(){MGraph*G;/*定义一个以邻接矩阵为存储类型的图G*/charchi,ch2;G=(MGraph*)malloc(sizcof(MGraph));printf("creategraph(adjoiningmatrix):〃)；/*创逮閔G的存储*/Creat