图的遍历1数据结构实验报告

1、南昌航空大学实验报告课程名称： 数据结构 实验名称： 实验八 图的遍历 班 级： 学生姓名： 学号： 指导教师评定： 签 名: 题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。一、 需求分析1. 用户可以根据自己的需求分别输入任意的一个有向图（可以是非连通图也可以是连通图）。2. 通过用广度优先遍历和深度优先遍历已有的图，并输出。3. 并且以邻接表的形式输出该已有的图。4. 程序执行的命令包括：（1）输入图的结点和弧构造图 （2）输出图 （2）广度优先遍历图 （3）深度优先遍历图 二、概要设计 为实现上述算法，需要链表的抽象数据类型：ADT Graph

2、数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。数据关系R：R=VRVR=|v,wV且P（v,w），表示从x到w的弧，谓词P（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，则返回该顶点在图中位置，否则返回其他信息。g

3、etvex(G,v)初始条件：图G存在，v是G中的某个顶点。操作结果：返回v的值。DFStraverse (G)初始条件：图G存在。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一次。BFStraverse (&S,e)初始条件：图G存在。操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一次。 ADT Graph2. 本程序有三个模块： 主程序模块 main()初始化；接受命令；显示结果； 创建图的模块：主要建立一个图；广度优先遍历和深度优先遍历模块：输出这两种遍历的结果；(4)输出图模块：显示已创建的图。三、详细设计元素类型，结点类型struct arcnode in

4、t 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; /*图的顶

5、点数*/int visit100; /*标志数组*/struct queue Q;2.对抽象数据类型中的部分基本操作的伪码算法如下：/*创建一个空队列*/struct queue initqueue() struct queue q; q.elem=(int *)malloc(maxsize*sizeof(int); if(!q.elem) exit(0); q.front=q.rear=0; return q;/*入队列*/struct queue enqueue(struct queue q,int v ) if(q.rear+1)%maxsize=q.front) printf(the

6、queue is full！n); else q.elemq.rear=v; q.rear=(q.rear+1)%maxsize; return q;/*出队列*/int dequeue(struct queue q) int cur; if(q.rear=q.front) printf(the queue is null!n); exit(0); else cur=q.elemq.front; q.front=(q.front+1)%maxsize; return cur; /*判断队列是否为空*/int emptyqueue(struct queue q) if(q.front=q.rea

7、r) return 1; else 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;ig.vexnum;i+) printf(di %d vexs information:,i); scanf(%d,&a); g.vexpexi.data=a; g.vexpexi

8、.firstarc=NULL; for(i=0;iadjvex=d; p-info=g.vexpexd.data; p-nextarc=g.vexpexs.firstarc; g.vexpexs.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,i,g.vexpexi.data); p=g.vexpexi.firstarc; while(p!=NULL) printf(%d,%

9、d)-,p-adjvex,p-info); p=p-nextarc; printf(n); /*连通图广度优先遍历*/void BFSsearch(struct graph g,int v) int i; struct arcnode *p; Q=initqueue(); printf(%5d,g.vexpexv.data); enqueue(Q,v); visitv=TURE; while(!emptyqueue(Q) i=dequeue(Q); p=g.vexpexi.firstarc; while(p!=NULL) enqueue(Q,p-adjvex); if(visitp-adjve

10、x=FALSE) printf(%5d,p-info); visitp-adjvex=TURE; p=p-nextarc; /*非连通图广度优先遍历*/void BFS(struct graph g) int i; for(i=0;ig.vexnum;i+) visiti=FALSE; for(i=0;iadjvex) DFSsearch(g,p-adjvex); p=p-nextarc; /*非连通图深度优先遍历*/void DFS(struct graph g) int i; for(i=0;ig.vexnum;i+) visiti=FALSE; for(i=0;ig.vexnum;i+)

11、 if(visiti=FALSE) DFSsearch(g,i); printf(nn);3.主函数和其他函数的伪码算法int main(void) struct graph g; int i; g=creatgraph(); displaygraph(g,n); printf(BFS result:n); BFS(g); printf(DFS result:n); DFS(g); getch(); return 1;4 函数调用关系maincreatgraph displaygraph BFS DFS BFSsearch DFSsearch initqueue dequeue enqueue

12、 四、调试分析本来想将图的顶点元素的类型定义为字符型的，但是在运行的时候发现在输入顶点数和弧数后，总是会在有字符没有输入就直接运行下一个语句了，改变了很多的方法，最后只有将顶点的类型定义为才解决了上述的问题。 在写程序的时候，开始creatgraph函数的部分代码为for(i=0;ig.vexnum;i+) printf(di %d vexs information:,i); scanf(%d,&a); g.vexpexi.data=a; g.vexpexi.firstarc=NULL; g.vexnum=n; g.arcnum=e;总是会有这样的提示“可能在g定义以前已经使用了在creatg

13、raph函数中”，经过多次的调试，最后代码改为g.vexnum=n; g.arcnum=e; for(i=0;i(1,10) 1,10-(3,15) 2,14-(1,10)-(0,17) 3,15-(4,13) 4,13-(2,14) 5,18-(7,20)-(6,19) 6,19 7,20-(6,19) 广度优先遍历的结果为17,10,14,15,13,18,19,20 深度优先遍历的结果为17,10,15,13,14,18,20,19七、附录：源程序 #include#include#define NULL 0#define FALSE 0#define TURE 1#define max

14、size 100struct 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

15、rear;int n; /*图的顶点数*/int visit100; /*标志数组*/struct queue Q;/*创建一个空队列*/struct queue initqueue() struct queue q; q.elem=(int *)malloc(maxsize*sizeof(int); if(!q.elem) exit(0); q.front=q.rear=0; return q;/*入队列*/struct queue enqueue(struct queue q,int v ) if(q.rear+1)%maxsize=q.front) printf(the queue is

16、 full！n); else q.elemq.rear=v; q.rear=(q.rear+1)%maxsize; return q;/*出队列*/int dequeue(struct queue q) int cur; if(q.rear=q.front) printf(the queue is null!n); exit(0); else cur=q.elemq.front; q.front=(q.front+1)%maxsize; return cur; /*判断队列是否为空*/int emptyqueue(struct queue q) if(q.front=q.rear) retur

17、n 1; else 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;ig.vexnum;i+) printf(di %d vexs information:,i); scanf(%d,&a); g.vexpexi.data=a; g.vexpexi.firstar

18、c=NULL; for(i=0;iadjvex=d; p-info=g.vexpexd.data; p-nextarc=g.vexpexs.firstarc; g.vexpexs.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,i,g.vexpexi.data); p=g.vexpexi.firstarc; while(p!=NULL) printf(%d,%d)-,p-adjvex,p-info); p=p-nextarc; printf(n); /*连通图广度优先遍历*/void BFSsearch(struct graph g,int v) int i; struct arcnode *p; Q=initqueue(); printf(%5d,g.vexpexv.data); enqueue(Q,v); visitv=TURE; while(