南昌航空大学实验报告
课程名称：数据结构实验名称：实验八图的遍历
班级：学生姓名：学号：
指导教师评定：签名:
题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。
一、需求分析
1.用户可以根据自己的需求分别输入任意的一个有向图（可以是非连通图也可以是连通
图）。
2.通过用广度优先遍历和深度优先遍历已有的图，并输出。
3.并且以邻接表的形式输出该已有的图。
4.程序执行的命令包括：
（1）输入图的结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图
二、概要设计
⒈为实现上述算法，需要链表的抽象数据类型：
ADT Graph {
数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={<v,w>|v,w∈V且P（v,w），<v,w>表示从x到w的弧，谓词P（v,w）定义了弧
<v,w>的意义或信息 }
酸碱中和基本操作P:
Creatgraph(&G,V,VR)
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
destroygraph(&G)
初始条件：图G存在。
操作结果：销毁图G。
displaygraph（G）
初始条件：图G存在。
操作结果：显示图G。
locatevex(G,u)
初始条件：图G存在，u和G中的顶点有相同的特征。
操作结果：若G中存在顶点u，则返回该顶点在图中位置，否则返回
其他信息。
getvex(G,v)
初始条件：图G存在，v是G中的某个顶点。
操作结果：返回v的值。
DFStraver (G)
初始条件：图G存在。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一
次。
BFStraver (&S,e)
初始条件：图G存在。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一
次。
}ADT Graph
2. 本程序有三个模块：
⑴主程序模块
main(){
初始化；
{
接受命令；
显示结果；
｝
｝
⑵创建图的模块：主要建立一个图；
⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；
(4)输出图模块：显示已创建的图。
三、详细设计
火鸡英文⒈元素类型，结点类型
struct arcnode
{ int adjvex; /*该弧所指向的顶点的位置*/
int info;
struct arcnode *nextarc; /*指向下一条弧的指针*/
};
struct vexnode
{ int data; /*顶点的信息*/
struct arcnode *firstarc; /*指向第一条依附该顶点的弧的指针*/
};
上海特色小吃struct graph
{ struct vexnode *vexpex;
int vexnum,arcnum; /*图的当前的顶点数和弧数*/
}；
/*定义队列*/
struct queue
{
int *elem;
int front;
int rear;
};
/*全局变量*/
int n; /*图的顶点数*/
int visit[100]; /*标志数组*/
struct queue Q;
2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个空队列*/
struct queue initqueue()
{ struct queue q;
q.elem=(int *)malloc(maxsize*sizeof(int)); if(!q.elem) exit(0);
q.ar=0;宝贝生日快乐
return q;
}
/*入队列*/
struct queue enqueue(struct queue q,int v ) { if((q.rear+1)%maxsize==q.front)
printf("the queue is full！！！\n");
el
{ q.ar]=v;
}
return q;
}
/*出队列*/
int dequeue(struct queue q)
{ int cur;
ar==q.front)
{ printf("the queue is null!!\n");
exit(0);
}
el
{ cur=q.elem[q.front];
q.front=(q.front+1)%maxsize;
return cur;
}
}
/*判断队列是否为空*/
int emptyqueue(struct queue q)
{ if(q.front==q.rear)
return 1;
el
return 0;
}
/*创建有向图*/
struct graph creatgraph()
{ int e,i,s,d;
int a;
struct graph g;
struct arcnode *p;
眉毛浓的女人printf("the number of vex(n) and arc(e):");
scanf("%d%d",&n,&e);
g.vexnum=n;
g.arcnum=e;
for(i=0;i<g.vexnum;i++)
{ printf("di %d vex's information:",i);
scanf("%d",&a);
g.vexpex[i].data=a;
g.vexpex[i].firstarc=NULL;
}
for(i=0;i<g.arcnum;i++)
{ printf("di %d arc's start,end:",i+1);
scanf("%d%d",&s,&d);
p=(struct arcnode *)malloc(sizeof(struct arcnode)); p->adjvex=d;
p->info=g.vexpex[d].data;
p->nextarc=g.vexpex[s].firstarc;
g.vexpex[s].firstarc=p;
}
return g;
}
/*显示有向图*/
void displaygraph(struct graph g,int n)
{ int i;
struct arcnode *p;
printf("diaplay the graph;\n");
for(i=0;i<n;i++)
{ printf(" [%d,%d]->",i,g.vexpex[i].data);
p=g.vexpex[i].firstarc;
while(p!=NULL)
{ printf("(%d,%d)->",p->adjvex,p->info);
碎花衬衫
p=p->nextarc;
}
printf("^\n");
}
}
/*连通图广度优先遍历*/
void BFSarch(struct graph g,int v) { int i;
struct arcnode *p;
Q=initqueue();
printf("%5d",g.vexpex[v].data);
enqueue(Q,v); visit[v]=TURE;
while(!emptyqueue(Q))
{ i=dequeue(Q);
p=g.vexpex[i].firstarc;
while(p!=NULL)
{ enqueue(Q,p->adjvex);
混凝土拌合物if(visit[p->adjvex]==FALSE) {
printf("%5d",p->info); visit[p->adjvex]=TURE; }
p=p->nextarc;大补元煎
}
}
}
/*非连通图广度优先遍历*/
void BFS(struct graph g)
{ int i;
for(i=0;i<g.vexnum;i++)
visit[i]=FALSE;
for(i=0;i<g.vexnum;i++)
if(visit[i]==FALSE)
BFSarch(g,i);
printf("\n\n");
}
/*连通图深度优先遍历*/
void DFSarch(struct graph g,int v)
