广度优先遍历(邻接表).doc

上机实验报告 学 院： 计算机与信息技术学院专 业： 计算机科学与技术(师范）课程名称： 数据结构实验题目：广度优先遍历（邻接表）班级序号： 师范1班学 号： 201421012731 学生姓名： 邓雪指导教师： 杨红颖完成时间： 2015年12月25号1、 实验目的：1掌握图的基本概念和邻接表存储结构。2掌握图的邻接表存储结构的算法实现。 3掌握图在邻接表存储结构上遍历算法的实现。二、实验环境： Windows 8.1 Microsoft Visual c+ 6.02、 实验内容及要求：编写图的广度优先遍历算法。四、概要设计：先定义图的邻接表数据，建立该图的邻接表，然后在用子函数写出广度优先搜索遍历的遍历算法，最后用主函数调用它们。 实现广度优先搜索遍历可以利用队列的原理。利用队列先进先出的特性，并设置访问标志实现连通图的广度优先搜索遍历。 广度优先搜索遍历类似于树的按层次遍历，对于用邻接表做存储结构的图，从某个给定顶点出发的图的遍历得到的访问结点顶点次序，随建立的邻接表的不同而可能不同。 将每个结点的边用一个单边表链接起来组成一个整体。所有头结点可看成一个一维数组，即邻接表所有链表中结点数目的一半为图中边数。占用的存储单元数目为n+2e。 抽象算法描述: （1）访问顶点i，并将其访问标志置为已被访问，即visitedi=true。（2）依次访问与标点i有边相连的所有顶点w1,w2-wt。（3）再按次序访问与w1,w2-wt有边相连且未曾访问过的顶点。（4）依此类推，直到图中所有顶点都被访问完。五、代码：#include #include #define maxsize 1024#define n 8#define e 9typedef char datatype;typedef char vextype;/定义结构体typedef structint datamaxsize;int front,rear;sequeue;/定义结构体typedef struct nodedatatype adjvex;struct node *next;edgenode;/定义结构体typedef structvextype vertex; edgenode *link;vexnode;sequeue *Q;vexnode gan;int visitedn;sequeue *sq;/建立无向图的邻接表void CREATADJLIST(vexnode ga)int i,j,k;edgenode *s;printf(读入树的结点信息：);for(i=0;in;i+)gai.vertex=getchar();gai.link=NULL;printf(读入边（vi,vj）的顶点对序号：);for(k=0;kadjvex=j;s-next=gai.link;gai.link=s;s=(edgenode *)malloc(sizeof(edgenode);s-adjvex=i;s-next=gaj.link;gaj.link=s;/置空队void SETNULL(sequeue *sq)sq-front=maxsize-1;sq-rear=maxsize-1;/判队空int EMPTY(sequeue *sq)if(sq-rear=sq-front)return 1;elsereturn 0;/入队int ENQUEUE(sequeue *sq,datatype x)if(sq-front=(sq-rear+1)%maxsize)printf(queue is full);return NULL;elsesq-rear=(sq-rear+1)%maxsize;sq-datasq-rear=x;return 1;/出队datatype DEQUEUE(sequeue *sq)if(EMPTY(sq)printf(queue is empty);return NULL;elsesq-front=(sq-front+1)%maxsize;return (sq-datasq-front);/广度优先遍历void BFSL(int k)int i;edgenode *p;Q=(sequeue *)malloc(sizeof(sequeue);SETNULL(Q);printf(%cn,gak.vertex);visitedk=1;ENQUEUE(Q,k);while(!EMPTY(Q)i=DEQUEUE(Q);p=gai.link;while(p!=NULL)if(!visitedp-adjvex)printf(%cn,gap-adjvex.vertex);visitedp-adjvex=1;ENQUEUE(Q,p-adjvex);p=p-next;void main()CREATADJLIST(ga);BFSL(0);六、运行界面七、实