广度优先遍历优质资料(可以直接使用，可编辑优质资料，欢迎下载）上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目：广度优先遍历（邻接表）班级序号：师范1班学号：202121012731学生姓名：邓雪指导教师：杨红颖完成时间：2021年12月25号实验目的：1﹒掌握图的基本概念和邻接表存储结构。2﹒掌握图的邻接表存储结构的算法实现。3﹒掌握图在邻接表存储结构上遍历算法的实现。二、实验环境：Windows8.1MicrosoftVisualc++6.0实验内容及要求：编写图的广度优先遍历算法。四、概要设计：先定义图的邻接表数据，建立该图的邻接表，然后在用子函数写出广度优先搜索遍历的遍历算法，最后用主函数调用它们。实现广度优先搜索遍历可以利用队列的原理。利用队列先进先出的特性，并设置访问标志实现连通图的广度优先搜索遍历。广度优先搜索遍历类似于树的按层次遍历，对于用邻接表做存储结构的图，从某个给定顶点出发的图的遍历得到的访问结点顶点次序，随建立的邻接表的不同而可能不同。将每个结点的边用一个单边表链接起来组成一个整体。所有头结点可看成一个一维数组，即邻接表所有链表中结点数目的一半为图中边数。占用的存储单元数目为n+2e。抽象算法描述:（1）访问顶点i，并将其访问标志置为已被访问，即visited[i]=true。（2）依次访问与标点i有边相连的所有顶点w1,w2------wt。（3）再按次序访问与w1,w2------wt有边相连且未曾访问过的顶点。（4）依此类推，直到图中所有顶点都被访问完。五、代码：#include<stdio.h>#include<stdlib.h>#definemaxsize1024#definen8#definee9typedefchardatatype;typedefcharvextype;//定义结构体typedefstruct{intdata[maxsize];intfront,rear;}sequeue;//定义结构体typedefstructnode{datatypeadjvex;structnode*next;}edgenode;//定义结构体typedefstruct{vextypevertex;edgenode*link;}vexnode;sequeue*Q;vexnodega[n];intvisited[n];sequeue*sq;//建立无向图的邻接表voidCREATADJLIST(vexnodega[]){inti,j,k;edgenode*s;printf("读入树的结点信息：");for(i=0;i<n;i++){ga[i].vertex=getchar();ga[i].link=NULL;}printf("读入边（vi,vj）的顶点对序号：");for(k=0;k<e;k++){scanf("%d%d",&i,&j);s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=ga[i].link;ga[i].link=s;s=(edgenode*)malloc(sizeof(edgenode));s->adjvex=i;s->next=ga[j].link;ga[j].link=s;}}//置空队voidSETNULL(sequeue*sq){sq->front=maxsize-1;sq->rear=maxsize-1;}//判队空intEMPTY(sequeue*sq){if(sq->rear==sq->front)return1;elsereturn0;}//入队intENQUEUE(sequeue*sq,datatypex){if(sq->front==(sq->rear+1)%maxsize){printf("queueisfull");returnNULL;}else{sq->rear=(sq->rear+1)%maxsize;sq->data[sq->rear]=x;return1;}}//出队datatypeDEQUEUE(sequeue*sq){if(EMPTY(sq)){printf("queueisempty");returnNULL;}else{sq->front=(sq->front+1)%maxsize;return(sq->data[sq->front]);}