if(visited[w]==0){
visit(w);
EnQueue(q,w);
visited[w]=1;
}
w=NextAdj(g,v);
}
}
}
void Travel_BFS(VNode g[],int visited[],int n){
int i;
for(i=0;i<n;i++){
visited[i]=0;
vertexType data;
Arcnode *firstarc;
}VNode;
//VNode G[MAX_VERTEX_NUM];
void getdata(VNode v);
//图的创建
void createGraph(int n,VNode G[]){
int i,e;
Arcnode *p,*q;
scanf("%d",&e);
while(e!=-1){
p=(Arcnode *)malloc(sizeof(Arcnode));
p->next=NULL;
p->adjvex=e;
if(G[i].firstarc==NULL){
G[i].firstarc=p;
}else{
q->next=p;
}
q=p;
}
}
//图的遍历(2)--广度优先搜索
void BFS(VNode G[],int v,int visited[]){
int w;
visit(v);
visited[v]=1;
EnQueue(q,v);
while(!emptyA(q)){
Dequeue(&q,&v);
w=FirstAdj(g,v);
while(w!=-1){
w=nextAdj(g,v);
}
}
void DFSGraph(VNode g[],int visited[],int n){
int i;
for(i=0;i<n;i++){
visited[i]=0;
}
for(i=0;i<n;i++){
if(visited[i]==0)
DFS(g,i,visited);
二、实验题目与要求
图的遍历
利用邻接矩阵或邻接表作为存储结构建立一个无向图，每个顶点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，顶点数不少于5个。要求分别以深度优先搜索(DFS)和广度优先搜索(BFS)进行遍历，输出遍历结果。
三、源代码清单
=#include<stdlib.h>
}
for(i=0;i<n;i++){
if(visited[i]==0)
BFS(g,i,visited);
}
}
实验心得：
通过本次实验，我理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。实验中遇到了很多问题，通过与同学交流沟通，最终完成了本次实验，希望以后能再接再厉。
#define MAX_VERTEX_NUM;
typedef int infoType;
typedef int vertexType;
typedef struct ArcNode{
int adjvex;
struct ArcNode *next;
infoType *weight;
}Arcnode;
typedef struct VNode{
printf("input the information of the vertex\n");
for(i=0;i<n;i++){
getdata(G[i]);
G[i].firstarc=NULL;
}
for(i=0;i<n;i++){
printf("create the edges for the %dth vertex\n",i);
scanf("%d",&e);
}
}
}
//图的遍历(1)--深度优先搜索
void DFS(VNode g[],int v,int visited[]){
int w;
visit(v);
visited[v]=1;
w=FirstAdj(g,v);
while(w!=-1){
if(visited[w]==0)
DFS(g,w,visited);
实验报告学院（系）名Fra bibliotek：计算机与通信工程学院
姓名
学号
专业
计算机科学与技术
班级
实验项目
实验四：图的深度优先与广度优先遍历
课程名称
数据结构与算法
课程代码
0661913
实验时间
2019年4月26日 第1-2节
实验地点
7-219
考核标准
实验过程
25分
程序运行
20分
回答问题
15分
实验报告
30分
特色
功能
5分
考勤违纪情况
5分
成绩
成绩栏
其它批改意见:
教师签字：
考核内容
评价在实验课堂中的表现，包括实验态度、编写程序过程等内容等。
□功能完善,
□功能不全
□有小错
□无法运行
○正确
○基本正确
○有提示
○无法回答
○完整
○较完整
○一般
○内容极少
○无报告
○有
○无
○有
○无
一、实验目的
理解图的逻辑特点，理解图的邻接矩阵或邻接表存储结构，掌握图的深度优先遍历、广度优先遍历算法。