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

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

1、实验四图的深度优先与广度优先遍历实验题目：从键盘输入的数据创建图（图的存储结构可采用邻接矩阵或邻接表），并对图进行深度优先搜索和广度优先搜索（1）算法设计思路简介先定义邻接矩阵和邻接表类型，实现邻接表和邻接矩阵的相互转换，输出邻接表和邻接矩阵，再实现深度和广度优先遍历在主程序中提供下列菜单：1…图的建立2…深度优先遍历图3…广度优先遍历图0…结束（2）算法描述：可以用自然语言、伪代码或流程图等方式VertexType;//顶点类型MGraph;//图的邻接矩阵类型ArcNode;//定义邻接表类型voidDi

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

3、lude#include#definemax100typedefstruct//以下定义临接矩阵类型{intnumber;intinfo;}VertexType;typedefstruct//图的定义{intedges[max][max];intn,e;VertexTypevexs[max];}MGraph;//定义邻接表类型typedefstructANode{intadjvex;structANode*nextarc;//指向下一条弧的指针intinfo;//存放弧的

4、信息（权值）}ArcNode;typedefstructVnode{intdata;ArcNode*firstarc;//指向第一条弧}VNode;typedefVNodeAdjList[max];//AdjList是邻接表类型，把大表变成几个小的连接到一起typedefstruct{AdjListadjlist;intn,e;//图中顶点数和和边数}ALGraph;intvisited[max];//全局数组用于判断后面节点是否被访问过voidDispMat(MGraphg)//输出邻接矩阵{inti,j;

5、for(i=0;i

6、指针域副初值G->adjlist[i].firstarc=NULL;for(i=0;iadjvex=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

7、;}voidDispAdj(ALGraph*G)//输出邻接表{inti;ArcNode*p;for(i=0;in;i++){p=G->adjlist[i].firstarc;if(p!=NULL)printf("%d:",i);while(p!=NULL){printf("%d",p->adjvex);//输出弧的终点p=p->nextarc;}printf("");}}voidchange(intvisited[],ALGraph*G)//给全局变量visited赋初值{inti;for(i=

8、0;in;i++)visited[i]=0;}voidListToMat(ALGraph*G,MGraphg)//将邻接表转换为邻接矩阵的形式{inti,j;intn=G->n;ArcNode*p;for(i=0;iadjlist[i].firstarc;while(p!