数据结构——图的基本操作

《数据结构——图的基本操作》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、广度优先遍历MBFS(MGraphg,ints,intn)(2)调用上述函数实现下列操作。①建立一个图的邻接矩阵和图的邻接表。②采用递归深度优先遍历输出图的邻接矩阵③采用递归深度优先遍历输出图的邻接表。④采用图的广度优先调历输出图的邻接表。⑤采用图的广度优先遍历输出图的邻接矩阵4．概要设计（1）：/**********************************图的基本操作**********************************///-------------------------------邻接矩阵数据类型的定义-------------------------------

3、-//最大顶点个数typedefstruct{charvexs[MAX_VERTEX_NUM];//顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//图当前顶点数和弧数}MGraph;//--------------------------------邻接表数据类型的定义----------------------------------typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置11福建师范大学物光院计算机教学辅导讲义structArcNode*nextarc;

4、//指向下一条弧的指针}ArcNode;typedefstructVNode{chardata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图当前顶点数和弧数}LGraph;（1）本程序主要包含6个函数：主函数main()建立图的邻接矩阵，邻接表Create_Graph()邻接表表示的图的递归深度优先遍历LDFS()邻接矩阵表示的图的递归深度优先遍历MDFS()邻接表表示的图的广度优先遍历LBFS()

5、邻接矩阵表示的图的广度优先遍历MBFS（）各函数间调用关系如下：mainCreate_Graph()LDFS()MDFS()LBFS()MBFS（）（2）主函数的伪码main(){定义邻接矩阵和邻接表；建立邻接矩阵和邻接表；邻接矩阵MDFS深度优先遍历；邻接矩阵MBFS广度优先遍历；邻接表LDFS深度优先遍历；邻接表LBFS广度优先遍历11福建师范大学物光院计算机教学辅导讲义}5详细设计/**********************************图的基本操作**********************************///---------------------------

6、----邻接矩阵数据类型的定义--------------------------------//最大顶点个数typedefstruct{charvexs[MAX_VERTEX_NUM];//顶点向量intacrs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//图当前顶点数和弧数}MGraph;//--------------------------------邻接表数据类型的定义----------------------------------typedefstructArcNode{intadjvex;//该弧所指向的顶

7、点的位置structArcNode*nextarc;//指向下一条弧的指针}ArcNode;typedefstructVNode{chardata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;//图当前顶点数