数据结构-实验8-图的基本操作.doc

《数据结构-实验8-图的基本操作.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、1．实验题目图的基本操作2．实验目的1)掌握图的邻接矩阵、邻接表的表示方法。2)掌握建立图的邻接矩阵的算法。3)掌握建立图的邻接表的算法。4)加深对图的理解，逐步培养解决实际问题的编程能力3．需求分析(1)编写图基本操作函数。①建立图的邻接表，邻接矩阵Create_Graph(LGraphlg.MGraphmg)②邻接表表示的图的递归深度优先遍历LDFS(LGraphg,inti)③邻接矩阵表示的图的递归深度优先遍历MDFS(MGraphg,inti,intvn)④邻接表表示的图的广度优先遍历LBFS(LGrap

2、hg,ints,intn)⑤邻接矩阵表示的图的广度优先遍历MBFS(MGraphg,ints,intn)(2)调用上述函数实现下列操作。①建立一个图的邻接矩阵和图的邻接表。②采用递归深度优先遍历输出图的邻接矩阵③采用递归深度优先遍历输出图的邻接表。④采用图的广度优先调历输出图的邻接表。⑤采用图的广度优先遍历输出图的邻接矩阵4．概要设计（1）结构体typedefstruct{charvexs[MAX_VERTEX_NUM];//顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

3、//邻接矩阵intvexnum,arcnum;//图当前顶点数和弧数}MGraph;typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{chardata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;in

4、tvexnum,arcnum;//图当前顶点数和弧数}LGraph;typedefstructQueue{intarry[MAX_VERTEX_NUM];intfront,rear;}Queue;（1）本程序主要包含6个函数：主函数main()建立图的邻接矩阵，邻接表Create_Graph()邻接表表示的图的递归深度优先遍历LDFS()邻接矩阵表示的图的递归深度优先遍历MDFS()邻接表表示的图的广度优先遍历LBFS()邻接矩阵表示的图的广度优先遍历MBFS（）各函数间调用关系如下：mainCreate_Gra

5、ph()LDFS()MDFS()LBFS()MBFS（）（1）主函数的伪码main(){定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历}5详细设计#include#include#include#include#defineOK1#defineERROR0#defineMAX_VERTEX_NUM33intvisited[MAX_

6、VERTEX_NUM];typedefstruct{intvexnum,arcnum;//图当前顶点数和弧数charvexs[MAX_VERTEX_NUM];//顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵}MGraph;typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{chardata;ArcNode*firstarc;}VNode,AdjLis

7、t[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}LGraph;typedefstructQueue{intarry[MAX_VERTEX_NUM];intfront,rear;}Queue;QueueQ;voidInitQueue(){Q.front=Q.rear=0;}intQueueEmpty(Queue*Q){if(Q->front==Q->rear)return1;elsereturn0;}voidEnQueue(Queu

8、e*Q,intw){if((Q->rear+1)%MAX_VERTEX_NUM==Q->front)printf("Error!");else{Q->arry[Q->rear]=w;Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;}}intDeQueue(Queue*Q){intu;if(Q->front==Q->rear)return-1;u=Q-