图的深度和广度优先遍历

数据结构课程实验报告课程名称数据结构班级计算123实验日期2023年6月1日--3日姓名学号实验成绩实验名称实验四图的深度和广度优先遍历实验目的及要求【实验目的】熟练掌握图的邻接表存储结构及其图的建立方法和深度和广度优先遍历的方法。【实验要求】图的存储可采用邻接矩阵或邻接表GraphCreate():按从键盘的数据建立图GraphDFS()：深度优先遍历图GraphBFS()：广度优先遍历图编写完整程序完成下面的实验内容并上机运行整理并上交实验报告实验环境硬件平台：普通的PC机软件平台：Windows7操作系统编程环境：VisualC++6.0实验内容以邻接矩阵或邻接表为存储结构，以用户指定的顶点为起始点，实现图的深度优先及广度优先搜索遍历，并输出遍历的结点序列。算法描述及实验步骤算法：1)定义图的邻接表存储结构2〕实现图的邻接表存储，即建立图的存储结构3〕实现图的深度优先遍历4〕定义队列的顺序存储结构，并实现队列的根本操作如初始化队列、入队、出对、判断队列是否为空等。利用队列实现图的广度优先遍历。伪代码：定义邻接矩阵和队列的存取结构；创立图L：置空图L->num=0；输入顶点数目num；i++,输入结点L->vexs[i]直到L->num;输出图L的各顶点；深度优先遍历图g中能访问的各个顶点输入起点的下标qidian；标志数组初始化mark[v]=0;for(v=qidian;v<g.num+qidian;v++)//{ v1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark);//从第v1个点出发深度优先遍历图g中能访问的各个顶点〔算法描述里的流程图很详细〕 }广度优先周游图g中能访问的各个顶点。构造空队列；入队a[0]；a[0]出队，a[0]的邻接点入队，遍历a[0]；队首出队，重复3直到队列为空；判断是否全遍历完了；输出广度优先遍历序列流程图：开始访问开始访问V0,置标志求V0邻接点有邻接点w求下一邻接点wV0W访问过结束NYNYDFS开始标志数组初始化Vi=1Vi访问过DFSVi=Vi+1Vi==Vexnums结束NNYY调试过程及实验结果总结本次试验采用的是邻接表的方式实现图的深度优先遍历和广度优先遍历。对于深度优先遍历，主要是采用递归的方式，广度优先遍历借助队列来实现。试验本身问题不是太大，但要注意输入的问题，什么时候用空格，什么时候用回车，这一点是需要注意的，因为一旦数据的输入有问题，结果当然也就不可能正确了。只有正确的输入数据，建立图，才能得出正确的遍历结果。附录#include<stdio.h>typedefintdatatype;#definemaxsize1024#definen100typedefcharVEXTYPE;typedeffloatADJTYPE;typedefstruct{ VEXTYPEvexs[n]; ADJTYPEarcs[n][n]; intnum;}GRAPH;//邻接矩阵数据类型typedefintDATATYPE;typedefstruct{ DATATYPEdata[maxsize]; intfront,rear;}SEQQUEUE;//队列数据类型voidGraphInit(GRAPH*L)//置空图{ L->num=0;}intGraphVexs(GRAPH*L)//求结点数{return(L->num);}voidGraphCreate(GRAPH*L)//创立图{ inti; GraphInit(L); printf("请输入顶点数目："); scanf("%d",&L->num); printf("请输入各顶点的信息(单个符号〕：\n"); for(i=0;i<L->num;i++) { fflush(stdin); scanf("%c",&L->vexs[i]); } printf("图已经创立完毕！");}voidGraphOut(GRAPHL)//图的输出{ inti; printf("\n图的顶点数目为：%d",L.num); printf("\n图的各顶点的信息为：\n"); for(i=0;i<L.num;i++) printf("%c",L.vexs[i]);}voidDFS(GRAPHg,intqidian,intmark[])//从第qidian个点出发深度优先遍历图g中能访问的各个顶点{ intv1; mark[qidian]=1; printf("%c",g.vexs[qidian]); for(v1=0;v1<g.num;v1++) { if(g.arcs[qidian][v1]!=0&&mark[v1]==0) DFS(g,v1,mark); }}voidGraphDFS(GRAPHg)//深度优先遍历图g中能访问的各个顶点{ intqidian,v,v1,mark[maxsize]; printf("\n深度优先遍历："); printf("\n请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0; } for(v=qidian;v<g.num+qidian;v++) { v1=v%g.num; if(mark[v1]==0) DFS(g,v1,mark); }}voidQueueInit(SEQQUEUE*sq)//建立空队列{sq->front=0;sq->rear=0;}intQueueIsEmpty(SEQQUEUEsq)//判断队列是否为空{if(sq.rear==sq.front)return(1);elsereturn(0);}intQueueFront(SEQQUEUEsq,DATATYPE*e)//保存队头元素{ if(QueueIsEmpty(sq)){ printf("queueisempty!\n");return0;}else{*e=sq.data[(sq.front)];return1;}}intQueueIn(SEQQUEUE*sq,DATATYPEx)//把元素x入队尾{ if(sq->front==(sq->rear+1)%maxsize) { printf("queueisfull!\n"); return0; } else { sq->data[sq->rear]=x; sq->rear=(sq->rear+1)%maxsize; return(1); }}intQueueOut(SEQQUEUE*sq)//删除队首元素{ if(QueueIsEmpty(*sq)) { printf("queueisempty!\n"); return0; } else { sq->front=(sq->front+1)%maxsize; return1;}}voidBFS(GRAPHg,intv,intmark[])//从v出发广度优先遍历图g中能访问的各个顶点{ intv1,v2; SEQQUEUEq; QueueInit(&q); QueueIn(&q,v); mark[v]=1; printf("%c",g.vexs[v]); while(QueueIsEmpty(q)==0) { QueueFront(q,&v1); QueueOut(&q); for(v2=0;v2<g.num;v2++) { if(g.arcs[v1][v2]!=0&&mark[v2]==0) { QueueIn(&q,v2); mark[v2]=1; printf("%c",g.vexs[v2]); } } }}voidGraphBFS(GRAPHg)//深度优先周游图g中能访问的各个顶点{ intqidian,v,v1,mark[maxsize]; printf("\n广度优先遍历："); printf("\n请输入起点的下标："); scanf("%d",&qidian); for(v=0;v<g.num;v++) { mark[v]=0;