实验四：图的遍历

实验报告学院〔系〕名称：计算机与通信工程学院姓名***学号***专业计算机科学与技术〔中外合作〕班级2023级6班实验工程实验四：图的遍历课程名称数据结构课程代码实验时间2023年12月11日实验地点计算机根底实验室210批改意见成绩教师签字：实验目的：理解图的逻辑特点；掌握理解图的两种主要存储结构〔邻接矩阵和邻接表〕，掌握图的构造、深度优先遍历、广度优先遍历算法。具体实验题目：每位同学按下述要求实现相应算法：根据从键盘输入的数据创立图〔图的存储结构可采用邻接矩阵或邻接表〕，并对图进行深度优先搜索和广度优先搜索〔实验类型：验证型〕1〕问题描述：在主程序中提供以下菜单： 1…图的建立 2…深度优先遍历图 3…广度优先遍历图 0…结束2〕实验要求：图的存储可采用邻接表或邻接矩阵；定义以下过程：CreateGraph():按从键盘的数据建立图DFSGrahp()：深度优先遍历图BFSGrahp()：广度优先遍历图【实验过程记录〔源程序、测试用例、测试结果及心得体会等〕】实验源程序如下#include<stdio.h>#include<stdlib.h>#defineMAX10//最大定点数typedefstructQNode//定义队列{ intdata; structQNode*next;}QNode;typedefstruct{ QNode*front; QNode*rear;}Queue;typedefstructArcNode//连接表构建图{ intadjvex; structArcNode*nextarc;}ArcNode;typedefstructVNode//头结点{ chardata; ArcNode*firstarc;//邻接链表头指针}VNode;typedefstruct{ VNodeadjlist[MAX]; intv,a;//图的顶点数和边数}Graph;intInitQueue(Queue*s)//构造一个空的对列{ s->front=s->rear=(QNode*)malloc(sizeof(QNode)); if(!s->front) return(0); s->front->next=NULL; return1;}Enqueue(Queue*s,inte)//入队列{ QNode*p; p=(QNode*)malloc(sizeof(QNode)); if(!p)return(0); p->data=e; p->next=NULL; s->rear->next=p; s->rear=p; return1;}DEQueue(Queue*q,int*e)//出队列{ QNode*p; if(q->front==q->rear)return1;//表示这是空对列 { p=q->front->next; *e=p->data;//附值 q->front->next=p->next; } if(q->rear==p)q->rear=q->front; free(p); return1;}intemptyQueue(Queue*q)//判断队列是否为空{ if(q->front==q->rear) return1; else return0;}voidCrerateGraph(Graph*G)//创立图{ inti,m,n; ArcNode*p; printf("请输入图的顶点数和边数:"); scanf("%d%d",&G->v,&G->a); getchar(); printf("请输入%d个顶点的信息:",G->v); for(i=0;i<G->v;i++) { scanf("%s",&G->adjlist[i].data);/*读入顶点信息*/ G->adjlist[i].firstarc=NULL;/*边表置为空表*/ } for(i=0;i<G->a;i++) { printf("输入第%d条边(起点序号，终点序号):",i+1); scanf("%d%d",&m,&n);//输入无序对顶点编号0开始 p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=n; p->nextarc=G->adjlist[m].firstarc; G->adjlist[m].firstarc=p; p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=m; p->nextarc=G->adjlist[n].firstarc; G->adjlist[n].firstarc=p; }}intvisited[MAX];voidDFSGraph(GraphG,inti)//深度优先遍历{ ArcNode*p; printf("访问顶点:%c\n",G.adjlist[i].data);/*访问顶点i*/ visited[i]=1; p=G.adjlist[i].firstarc; while(p)/*从p的邻接点出发进行深度优先搜索*/ {if(!visited[p->adjvex]) DFSGraph(G,p->adjvex); p=p->nextarc;//找指向下一条弧的指针 }}voidDFSTraverse(GraphG){inti;for(i=0;i<G.v;i++)visited[i]=0;/*初始化标志数组*/for(i=0;i<G.v;i++)if(!visited[i])/*vi未访问过*/DFSGraph(G,i);//函数的递归的使用}intvisit[MAX];voidBFSGraph(GraphG)//广度优先遍历{ inti,k; Queueq; ArcNode*p; for(i=0;i<G.v;i++); visit[i]=0; InitQueue(&q); for(i=0;i<G.v;i++) if(!visit[i]) { printf("访问顶点:%c\n",G.adjlist[i].data); visit[i]=1; Enqueue(&q,i); while(!emptyQueue(&q)) { DEQueue(&q,&k); p=G.adjlist[k].firstarc; while(p) { if(!visited[p->adjvex]) { printf("访问顶点:%c\n",G.adjlist[p->adjvex].data); visited[p->adjvex]=1; Enqueue(&q,p->adjvex); } p=p->nextarc; } } }}voidmain()//主程序{ inta,i,j; Graph*G;G=(Graph*)malloc(sizeof(Graph)); while(a) { printf("请输入1~4，运行其功能\n"); printf("1……图的建立(本程序最多包含的点数为10)\n"); printf("2……深度优先遍历图\n"); printf("3……广度优先遍历图\n"); printf("4……结束\n"); scanf("%d",&a); getchar(); switch(a){ case1: CrerateGraph(G);break; case2: DFSTraverse(*G);break; case3:BFSGraph(*G);break; default:exit(4); } }}测试用例及测试结果如下：深度优先遍历输出结果：13542广度优先遍历输出结果：12345实验设计思路：〔1〕图的创立我采用的是连接表储存结构，将图的顶点、边的信息分别存在连接表的data