广度优先遍历(邻接表)

《广度优先遍历(邻接表)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、上机实验报告学院：计算机与信息技术学院专业：计算机科学与技术(师范）课程名称：数据结构实验题目：广度优先遍历（邻接表）班级序号：师范1班学号：201421012731学生姓名：邓雪指导教师：杨红颖完成时间：2015年12月25号一、实验目的：1﹒掌握图的基本概念和邻接表存储结构。 2﹒掌握图的邻接表存储结构的算法实现。 3﹒掌握图在邻接表存储结构上遍历算法的实现。二、实验环境：Windows8.1MicrosoftVisualc++6.0二、实验内容及要求：编写图的广度优先遍历算法。四、概要设计：先定义图的邻接表数据，建立该图的邻接表，然后

2、在用子函数写出广度优先搜索遍历的遍历算法，最后用主函数调用它们。 实现广度优先搜索遍历可以利用队列的原理。利用队列先进先出的特性，并设置访问标志实现连通图的广度优先搜索遍历。 广度优先搜索遍历类似于树的按层次遍历，对于用邻接表做存储结构的图，从某个给定顶点出发的图的遍历得到的访问结点顶点次序，随建立的邻接表的不同而可能不同。 将每个结点的边用一个单边表链接起来组成一个整体。所有头结点可看成一个一维数组，即邻接表所有链表中结点数目的一半为图中边数。占用的存储单元数目为n+2e。 抽象算法描述: （1）访问顶点i，并将其访问标志置为已被访问，即

3、visited[i]=true。 （2）依次访问与标点i有边相连的所有顶点w1,w2------wt。（3）再按次序访问与w1,w2------wt有边相连且未曾访问过的顶点。 （4）依此类推，直到图中所有顶点都被访问完。五、代码：#include#include#definemaxsize1024#definen8#definee9typedefchardatatype;typedefcharvextype;//定义结构体typedefstruct{intdata[maxsize];intfront,

4、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=

5、0;iadjvex=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].

6、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-

7、>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));SE

8、TNULL(Q);printf("%c",ga[k].vertex);visited[k]=1;ENQUEUE(Q,k);while(!EMPTY(Q)){i=DEQUEUE