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

上机实验报告
学院：计算机与信息技术学院
专业：计算机科学与技术(师范）
课程名称：数据结构
实验题目:广度优先遍历(邻接表)
班级序号:师范1班
学号: 201421012731
学生姓名:邓雪
指导教师:杨红颖
完成时间:2015年12月25号
一、 实验目的：
1﹒掌握图的基本概念和邻接表存储结构. 
2﹒掌握图的邻接表存储结构的算法实现。 
3﹒掌握图在邻接表存储结构上遍历算法的实现。
二、实验环境:
Windows 8。1
Microsoft Visual c++ 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〉
＃define maxsize 1024
#define n 8
#define e 9
typedef char datatype;
typedef char vextype;
//定义结构体
typedef struct
｛
int data［maxsize］；
int front，rear;
｝sequeue;
//定义结构体
typedef struct node
｛
datatype adjvex；
struct node *next；
}edgenode;
//定义结构体
typedef struct
{
vextype vertex;
edgenode *link；
}vexnode;
sequeue ＊Q；
vexnode ga［n］；
int visited［n］;
sequeue ＊sq;
//建立无向图的邻接表
void CREATADJLIST（vexnode ga[]）
｛
int i，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；
｝
｝
//置空队
void SETNULL（sequeue ＊sq)
｛
sq->front=maxsize—1；
sq—〉rear=maxsize—1；
｝
//判队空
int EMPTY(sequeue ＊sq）
{
if(sq-〉rear==sq-〉front）
return 1；
else
return 0;
}
//入队
int ENQUEUE(sequeue ＊sq,datatype x)
｛
if（sq—〉front==(sq—〉rear+1）％maxsize）
{
printf（”queue is full"）；
return NULL；
}
else
｛
sq—>rear=(sq-〉rear+1)％maxsize；
sq—〉data［sq->rear］=x；
return 1;
｝
}
//出队
datatype DEQUEUE(sequeue ＊sq）
｛
if（EMPTY(sq））
｛
printf（"queue is empty”）；
return NULL；
｝
else
｛
sq->front=（sq—〉front+1)％maxsize；
return （sq-〉data［sq—〉front]）；
｝
}
//广度优先遍历
void BFSL（int k）
{
int i;
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;
｝
}
｝
void main（）
｛
CREATADJLIST（ga）;
BFSL（0）；}
六、运行界面
七、实验中遇到的问题及总结
在图的存储的基础上广度优先遍历使我对图的基本知识更加了解，更加扎实。并且更加明确广度优先遍历和深度优遍历的区别和联系。在实验中我希望我可以更加的细心,更上一层楼.
八、参考文献
《数据结构——用C语言描述》