实验四 图的深度优先与广度优先遍历.doc

《实验四 图的深度优先与广度优先遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验四图的深度优先与广度优先遍历实验时间：2011年5月12日，12:50-15:50（地点：7-215）实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构（邻接矩阵和邻接表），掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目：（任课教师根据实验大纲自己指定）每位同学按下述要求实现相应算法：根据从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索1）问题描述：在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束2）实验要求：图的存

2、储可采用邻接表或邻接矩阵；定义下列过程：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图（1）算法设计思路简介先定义邻接矩阵和邻接表类型，实现邻接表和邻接矩阵的相互转换，输出邻接表和邻接矩阵，再实现深度和广度优先遍历（2）算法描述：可以用自然语言、伪代码或流程图等方式VertexType;//顶点类型MGraph;//图的邻接矩阵类型ArcNode;//定义邻接表类型voidDispMat(MGraphg)//输出邻接矩阵voidMatToList

3、(MGraphg,ALGraph*&G)//将邻接矩阵g转换为邻接表GvoidDispAdj(ALGraph*G)//输出邻接表voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式voidDFS(ALGraph*G,intv)//递归深度优先遍历voidBFS(ALGraph*G,intv)//广度优先遍历（3）算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等有个问题，不知如何实现输入矩阵源代码：#include#include

4、#definemax100//最大顶点个数typedefstruct//以下定义临接矩阵类型{intnumber;//顶点编号intinfo;//顶点其他信息,边的权值}VertexType;//顶点类型typedefstruct//图的定义{intedges[max][max];//邻接矩阵intn,e;//顶点数和弧数VertexTypevexs[max];//存放定点信息}MGraph;//图的邻接矩阵类型//定义邻接表类型typedefstructANode//弧的结点结构类型{intadj

5、vex;//弧的重点位置,就是放值的structANode*nextarc;//指向下一条弧的指针intinfo;//存放弧的信息（权值）}ArcNode;typedefstructVnode{intdata;//邻接表头结点的的类型ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[max];//AdjList是邻接表类型，把大表变成几个小的连接到一起typedefstruct{AdjListadjlist;//邻接表intn,e;//图中顶点数和和边数}ALGra

6、ph;//图的邻接表类型intvisited[max];//全局数组用于判断后面节点是否被访问过voidDispMat(MGraphg)//输出邻接矩阵{inti,j;for(i=0;i

7、n;//n为顶点数ArcNode*p;//弧节点结构的类型G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;iadjlist[i].firstarc=NULL;for(i=0;iadj

8、vex=j;//这是小节点的放值的域，只要他的列值，链式表只要说明节点之间有关系就行，指终点位置p->info=g.edges[i][j];//存放边的权值p->nextarc=G->adjlist[i].firstarc;//将*p连接到表后G->adjlist[i].firstarc=p;}G->e=g.e;G->n=g.n;