广度优先遍历优质资料

广度优先遍历优质资料(可以直接使用，可编辑优质资料，欢迎下载）

广度优先遍历优质资料(可以直接使用，可编辑优质资料，欢迎下载）上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目：广度优先遍历（邻接表）班级序号：师范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]);}}//广度优先遍历voidBFSL(intk){inti;edgenode*p;Q=(sequeue*)malloc(sizeof(sequeue));SETNULL(Q);printf("%c\n",ga[k].vertex);visited[k]=1;ENQUEUE(Q,k);while(!EMPTY(Q)){i=DEQUEUE(Q);p=ga[i].link;while(p!=NULL){if(!visited[p->adjvex]){printf("%c\n",ga[p->adjvex].vertex);visited[p->adjvex]=1;ENQUEUE(Q,p->adjvex);}p=p->next;}}}voidmain(){CREATADJLIST(ga);BFSL(0);}六、运行界面七、实验中遇到的问题及总结在图的存储的基础上广度优先遍历使我对图的基本知识更加了解，更加扎实。并且更加明确广度优先遍历和深度优遍历的区别和联系。在实验中我希望我可以更加的细心，更上一层楼。八、参考文献《数据结构——用C语言描述》实验五图的表示与遍历一、实验目的1、掌握图的邻接矩阵和邻接表表示2、掌握图的深度优先和广度优先搜索方法3、理解图的应用方法二、实验预习说明以下概念1、深度优先搜索遍历：从根开始一个一个搜索2、广度优先搜索遍历：从根的邻接点出发依次访问3、拓扑排序：一个无指向的点开始排序4、最小生成树：最小权的生成树5、最短路径：路径权数最小三、实验内容和要求1、阅读并运行下面程序，根据输入写出运行结果。#include<stdio.h>#defineN20#defineTRUE1#defineFALSE0intvisited[N];typedefstruct/*队列的定义*/{intdata[N];intfront,rear;}queue;typedefstruct/*图的邻接矩阵*/{intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph(graph*g);/*建立一个无向图的邻接矩阵*/voiddfs(inti,graph*g);/*从第i个顶点出发深度优先搜索*/voidtdfs(graph*g);/*深度优先搜索整个图*/voidbfs(intk,graph*g);/*从第k个顶点广度优先搜索*/voidtbfs(graph*g);/*广度优先搜索整个图*/voidinit_visit();/*初始化访问标识数组*/voidcreateGraph(graph*g)/*建立一个无向图的邻接矩阵*/{inti,j;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;/*顶点数目*/for(i=0;i<g->vexnum;i++)/*邻接矩阵初始化*/for(j=0;j<g->vexnum;j++)g->arcs[i][j]=0;printf("输入边的信息：\n");scanf("%d,%d",&i,&j);/*读入边i,j*/while(i!=-1)/*读入i,j为－1时结束*/{g->arcs[i][j]=1;g->arcs[j][i]=1;scanf("%d,%d",&i,&j);}}voiddfs(inti,graph*g)/*从第i个顶点出发深度优先搜索*/{intj;printf("%c",g->vexs[i]);visited[i]=TRUE;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j]))dfs(j,g);}voidtdfs(graph*g)/*深度优先搜索整个图*/{inti;printf("\n从顶点%C开始深度优先搜索序列：",g->vexs[0]);for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)dfs(i,g);}voidbfs(intk,graph*g)/*从第k个顶点广度优先搜索*/{inti,j;queueqlist,*q;q=&qlist;q->rear=0;q->front=0;printf("%c",g->vexs[k]);visited[k]=TRUE;q->data[q->rear]=k;q->rear=(q->rear+1)%N;while(q->rear!=q->front){i=q->data[q->front];q->front=(q->front+1)%N;for(j=0;j<g->vexnum;j++)if((g->arcs[i][j]==1)&&(!visited[j])){printf("%c",g->vexs[j]);visited[j]=TRUE;q->data[q->rear]=j;q->rear=(q->rear+1)%N;}}}voidtbfs(graph*g)/*广度优先搜索整个图*/{inti;printf("\n从顶点%C开始广度优先搜索序列：",g->vexs[0]);for(i=0;i<g->vexnum;i++)if(visited[i]!=TRUE)bfs(i,g);}voidinit_visit()/*初始化访问标识数组*/{inti;for(i=0;i<N;i++)visited[i]=FALSE;}intmain(){graphga;inti,j;createGraph(&ga);printf("无向图的邻接矩阵：\n");for(i=0;i<ga.vexnum;i++){for(j=0;j<ga.vexnum;j++)printf("%3d",ga.arcs[i][j]);printf("\n");}init_visit();tdfs(&ga);init_visit();tbfs(&ga);return0;}根据右图的结构验证实验，输入：ABCDEFGH#ABABCDEFGH012345670,20,51,31,42,52,63,74,7-1,-1运行结果：2、阅读并运行下面程序，补充拓扑排序算法。#include<stdio.h>#include<malloc.h>#defineN20typedefstructedgenode{/*图的邻接表：邻接链表结点*/intadjvex;/*顶点序号*/structedgenode*next;/*下一个结点的指针*/}edgenode;typedefstructvnode{/*图的邻接表：邻接表*/chardata;/*顶点信息*/intind;/*顶点入度*/structedgenode*link;/*指向邻接链表指针*/}vnode;voidcreateGraph_list(vnodeadjlist[],int*p)；/*建立有向图的邻接表*/voidtopSort(vnodeg[],intn)；/*拓扑排序*/voidcreateGraph_list(vnodeadjlist[],int*p){/*建立有向图的邻接表*/inti,j,n,e;charv;edgenode*s;i=0;n=0;e=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){adjlist[i].data=v;/*读入顶点信息*/adjlist[i].link=NULL;adjlist[i].ind=0;i++;}n=i;*p=n;/*建立邻接链表*/printf("\n请输入弧的信息(i=-1结束)：i,j:\n");scanf("%d,%d",&i,&j);while(i!=-1){s=(structedgenode*)malloc(sizeof(edgenode));s->adjvex=j;s->next=adjlist[i].link;adjlist[i].link=s;adjlist[j].ind++;/*顶点j的入度加1*/e++;scanf("%d,%d",&i,&j);}printf("邻接表:");for(i=0;i<n;i++){/*输出邻接表*/printf("\n%c,%d:",adjlist[i].data,adjlist[i].ind);s=adjlist[i].link;while(s!=NULL){printf("->%d",s->adjvex);s=s->next;}}}voidtopSort(vnodeg[],intn){/*拓扑排序*/}intmain(){vnodeadjlist[N];intn,*p;p=&n;createGraph_list(adjlist,p);return0;}根据输入，输出有向图的拓扑排序序列。并画出有向图。输入:ABCDEF#0,11,22,34,14,5-1,-1运行结果：3、阅读并运行下面程序。#include<stdio.h>#defineN20#defineTRUE1#defineINF32766/*邻接矩阵中的无穷大元素*/#defineINFIN32767/*比无穷大元素大的数*/typedefstruct{/*图的邻接矩阵*/intvexnum,arcnum;charvexs[N];intarcs[N][N];}graph;voidcreateGraph_w(graph*g,intflag);voidprim(graph*g,intu);voiddijkstra(graphg,intv);voidshowprim();voidshowdij();/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/voidcreateGraph_w(graph*g,intflag){inti,j,w;charv;g->vexnum=0;g->arcnum=0;i=0;printf("输入顶点序列(以#结束)：\n");while((v=getchar())!='#'){g->vexs[i]=v;/*读入顶点信息*/i++;}g->vexnum=i;for(i=0;i<6;i++)/*邻接矩阵初始化*/for(j=0;j<6;j++)g->arcs[i][j]=INF;printf("输入边的信息：\n");scanf("%d,%d,%d",&i,&j,&w);/*读入边(i,j,w)*/while(i!=-1)/*读入i为－1时结束*/{g->arcs[i][j]=w;if(flag==1)g->arcs[j][i]=w;scanf("%d,%d,%d",&i,&j,&w);}}voidprim(graph*g,intu)/*出发顶点u*/{intlowcost[N],closest[N],i,j,k,min;for(i=0;i<g->vexnum;i++)/*求其他顶点到出发顶点u的权*/{lowcost[i]=g->arcs[u][i];closest[i]=u;}lowcost[u]=0;for(i=1;i<g->vexnum;i++)/*循环求最小生成树中的各条边*/{min=INFIN;for(j=0;j<g->vexnum;j++)/*选择得到一条代价最小的边*/if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("(%c,%c)--%d\n",g->vexs[closest[k]],g->vexs[k],lowcost[k]);/*输出该边*/lowcost[k]=0;/*顶点k纳入最小生成树*/for(j=0;j<g->vexnum;j++)/*求其他顶点到顶点k的权*/if(g->arcs[k][j]!=0&&g->arcs[k][j]<lowcost[j]){lowcost[j]=g->arcs[k][j];closest[j]=k;}}}voidprintPath(graphg,intstartVex,intEndVex){intstack[N],top=0;/*堆栈*/inti,k,j;intflag[N];/*输出路径顶点标志*/k=EndVex;for(i=0;i<g.vexnum;i++)flag[i]=0;j=startVex;printf("%c",g.vexs[j]);flag[j]=1;stack[top++]=k;while(top>0)/*找j到k的路径*/{for(i=0;i<g.vexnum;i++){if(path[k][i]==1&&flag[i]==0)/*j到k的路径含有i顶点*/{if(g.arcs[j][i]!=INF)/*j到i的路径含有中间顶点*/{printf("->%c(%d)",g.vexs[i],g.arcs[j][i]);/*输出j到k的路径的顶点i*/flag[i]=1;j=i;k=stack[--top];break;}else{if(i!=k)stack[top++]=i;/*break;*/}}}}voiddijkstra(graphg,intv){/*dijkstra算法求单源最短路径*/intpath[N][N],dist[N],s[N];intmindis,i,j,u,k;for(i=0;i<g.vexnum;i++){dist[i]=g.arcs[v][i];s[i]=0;for(j=0;j<g.vexnum;j++)path[i][j]=0;if(dist[i]<INF){path[i][v]=1;path[i][i]=1;}}dist[v]=0;s[v]=1;for(i=0,u=1;i<g.vexnum;i++){mindis=INFIN;for(j=0;j<g.vexnum;j++)if(s[j]==0)if(dist[j]<mindis){u=j;mindis=dist[j];}s[u]=1;for(j=0;j<g.vexnum;j++)if((s[j]==0)&&dist[u]+g.arcs[u][j]<dist[j]){dist[j]=dist[u]+g.arcs[u][j];for(k=0;k<g.vexnum;k++)path[j][k]=path[u][k];path[j][j]=1;}}printf("\n顶点%c->到各顶点的最短路径\n",g.vexs[v]);for(i=0;i<g.vexnum;i++){printf("\n顶点%c->顶点%c：",g.vexs[v],g.vexs[i]);if(dist[i]==INF||dist[i]==0)printf("无路径");else{printf("%d",dist[i]);printf("经过顶点：");printPath(g,v,i);/*输出v到i的路径*/}}}voidshowprim()/*最小生成树prim算法演示*/{graphga;createGraph_w(&ga,1);prim(&ga,0);}voidshowdij(){/*dijstra算法演示*/graphga;createGraph_w(&ga,0);dijkstra(ga,0);}intmain(){showprim();/*prim算法演示*/getchar();showdij();/*dijstra算法演示*/return0;}下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求其最小生成树；输入的第二部分为有向图，求其最短路径。最小生成树最短路径ABCDEF#0,1,60,2,10,3,51,2,51,4,32,3,52,4,62,5,43,5,24,5,6-1,-1,-1ABCDEF#0,2,100,5,1000,4,301,2,52,3,503,4,203,5,104,3,204,5,60-1,-1,-1运行结果：（并画出两个图）最小生成树最短路径四、实验小结图的表示和变厉需要很强的逻辑性五、教师评语数据结构实验报告-顺序表的创建、遍历及有序合并操作二、实验内容与步骤实现顺序表的创建、遍历及有序合并操作，基本数据结构定义如下：typedefintElemType;#defineMAXSIZE100#defineFALSE0#defineTRUE1typedefstruct{ElemTypedata[MAXSIZE];intlength;}seqlist;创建顺序表，遍历顺序表#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100#defineIcreament20#defineFALSE0#defineTRUE1typedefintElemType;//用户自定义数据元素类型//顺序表结构体的定义typedefstruct{ElemType*elem;//顺序表的基地址intlength;//顺序表的当前长度intlistsize;//预设空间容量}SqList;//线性表的顺序存储结构SqList*InitList()//创建空的顺序表{SqList*L=(SqList*)malloc(sizeof(SqList));//定义顺序表Lif(!L){printf("空间划分失败，程序退出\n");returnNULL;}L->elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));if(!L->elem){printf("空间划分失败，程序退出\n");returnNULL;}L->length=0;L->listsize=MAXSIZE;returnL;}intCreateList(SqList*L)//创建顺序表（非空）{intnumber;//顺序表中元素的个数inti;//循环变量printf("请输入顺序表中元素的个数：");scanf("%d",&number);if(number>MAXSIZE)//一定要判断输入的个数是否大于顺序表的最大长度{printf("输入个数大于顺序表的长度\n");return0;}for(i=0;i<number;i++){printf("输入第%d个数:",i+1);scanf("%d",L->elem+i);//L->elem+i：每次的输入都保存在顺序表元素中的下一个地址，而不是一直放在元素的首地址}//给顺序表中每个数据元素赋值L->length=number;//当前顺序表的长度return1;}voidprint(SqList*L)//遍历顺序表{inti; printf("\n开始遍历顺序表\n");for(i=0;i<L->length;i++){printf("%d",*(L->elem+i));//L->elem+i：和输入是一个道理} printf("\n遍历结束\n");printf("\n");}intmain(){SqList*L=InitList();//申请一个指向顺序表的指针，并对其初始化if(!L)//判断申请是否成功{printf("初始化线性表失败\n");return1;}if(!CreateList(L))//判断创建顺序表是否成功{printf("创建顺序表失败\n");return1;}print(L);//打印顺序表与上面遍历顺序表相对应，若没有就不遍历free(L->elem);//释放申请的顺序表元素的内存free(L);//释放申请的顺序表内存return0;}表的有序合并#include<stdio.h>#include<stdlib.h>#defineMAXSIZE100typedefintElemType;//顺序表结构体的定义typedefstruct{ ElemTypedata[MAXSIZE]; intsize;}seqlist;//函数声明voidinit(seqlist*slt);voiddisplay(seqlistslt);voidsort(seqlist*s);