广度优先遍历(邻接表)

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

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

3、被访问，即visitedi=true。 （2）依次访问与标点i有边相连的所有顶点w1,w2-wt。（3）再按次序访问与w1,w2-wt有边相连且未曾访问过的顶点。 （4）依此类推，直到图中所有顶点都被访问完。五、代码：#include <stdio.h>#include <stdlib.h>#define maxsize 1024#define n 8#define e 9typedef char datatype;typedef char vextype;/定义结构体typedef structint datamaxsize;int front,r

4、ear;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;i<n;i+)gai.

5、vertex=getchar();gai.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=gai.link;gai.link=s;s=(edgenode *)malloc(sizeof(edgenode);s->adjvex=i;s->next=gaj.link;gaj.link=s;/置空队voi

6、d 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)%m

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