广度优先遍历(邻接表)

上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目:广度优先遍历(邻接表)班级序号:师范1班学号:201421012731学生姓名:邓雪指导教师:杨红颖完成时间:2015年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）；}六、