课程名称：数据结构实验名称：实验八图的遍历
班级：学生姓名：学号：
指导教师评定：签名:
题目：假设无向图采用邻接表结构表示。编程分别实现图的深度优先搜索算法和广度优先搜索算法。
一、需求分析
1.用户可以根据自己的需求进行输入所需的图（可以是非连通图也可以是连通图），其中1
表示创建一个有向图，2表示创建一个无向图。
2.用户进入菜单页面选择输入图的状态（1表示创建一个有向图，2表示创建一个无向图，
3表示输出已创建的图，4表示深度优先遍历已有的图，5表示广度优先遍历已有的图，6表示退出程序状态）。
3.程序执行的命令包括：
（1）输入图的结点和弧构造图（2）输出图（2）广度优先遍历图（3）深度优先遍历图
二、概要设计
⒈为实现上述算法，需要链表的抽象数据类型：
ADT Graph {
数据对象V：V是具有相同特征的数据元素的集合，称为顶点集。
数据关系R：
R={VR}
VR={ 基本操作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的值。 DFStraverse (G) 初始条件：图G存在。 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点访问一 次。 BFStraverse (&S,e) 初始条件：图G存在。 操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点访问一 次。 }ADT Graph 2. 本程序有三个模块： ⑴主程序模块 main(){ 初始化； Switch（参数）{ Case 1 ：接受命令（用户创建一个有向图）； Case 2 ：接受命令（用户创建一个无向图）； Case 3 ：接受命令（输出已创建的图）； Case 4 ：接受命令（深度优先遍历已有的图）； Case 5 ：接受命令（广度优先遍历已有的图）； Case 6 ：接受命令（退出程序）； ｝ ｝ ⑵创建图的模块：主要建立一个图； ⑶广度优先遍历和深度优先遍历模块：输出这两种遍历的结果； (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.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 full！！！\\n"); else { q.elem[q.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.elem[q.front]; q.front=(q.front+1)%maxsize; return cur; } } /*判断队列是否为空*/int emptyqueue(struct queue q) { if(q.front==q.rear) return 1; else return 0; } /*创建有向图*/ struct graph creatgraph1() { 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 g.vexnum=n; g.arcnum=e; for(i=0;i scanf("%d g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i scanf("%d%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; } /*创建无向图*/ struct graph creatgraph2() { int e,i,s,d; int a; struct graph g; struct arcnode *p,*q; printf("the number of vex(n) and arc(e):"); scanf("%d%d g.vexnum=n; g.arcnum=e; for(i=0;i g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i scanf("%d%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; q=(struct arcnode *)malloc(sizeof(struct arcnode)); q->adjvex=s; q->info=g.vexpex[s].data; q->nextarc=g.vexpex[d].firstarc; g.vexpex[d].firstarc=q; } return g; } /*显示有向图*/ void displaygraph(struct graph g,int n) { int i; struct arcnode *p; printf("diaplay the graph;\\n"); for(i=0;i p=g.vexpex[i].firstarc; while(p!=NULL) { printf("(%d,%d)-> p=p->nextarc; } printf("^\\n"); } } /*连通图广度优先遍历*/ void BFSsearch(struct graph g,int v) { int i; struct arcnode *p; Q=initqueue(); printf("%5d 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 visit[p->adjvex]=TURE; } p=p->nextarc; } } } /*非连通图广度优先遍历*/ void BFS(struct graph g) { int i; printf("BFS result:\\n"); for(i=0;i for(i=0;i BFSsearch(g,i); printf("\\n\\n"); } /*连通图深度优先遍历*/ void DFSsearch(struct graph g,int v) { struct arcnode *p; printf("%5d p=g.vexpex[v].firstarc; while(p!=NULL) { if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc; } } /*非连通图深度优先遍历*/ void DFS(struct graph g) { int i; printf("DFS result:\\n"); for(i=0;i printf("\\n\\n"); } /*-----主菜单定义-----*/ int menu_select() { char s[80]; int c; gotoxy(1,25); /*将光标定在第25行第1列*/ printf("press any key enter menu ......\\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/ clrscr(); /*清屏*/ gotoxy(1,1); printf("***************MENU***************\\n\\n"); printf(" 1. Make a digraph by youself!\\n"); printf(" 2. Make a undigraph by youself!\\n"); printf(" 3. Ontput your graph!\\n"); printf(" 4. Depth_first search your graph!\\n"); printf(" 5. Bredth_first search your graph!\\n"); printf(" 6. Quit!\\n"); printf("**********************************\\n"); do{ printf("\\n Enter you choice (1~6):\\n"); /*提示输入选项*/ scanf("%s c=atoi(s); /*将输入的字符串转化为整型*/ }while(c<1||c>6); return c; } 3.主函数和其他函数的伪码算法 void main() { struct graph g; int i; clrscr(); /*清屏*/ for(;;) { switch(menu_select()) { case 1: { clrscr(); g=creatgraph1(); break; } case 2: { clrscr(); g=creatgraph2(); break; } case 3: { clrscr(); printf("diaplay the graph;\\n"); displaygraph(g,n); break; } case 4: { clrscr(); printf("DFS result:\\n"); DFS(g); break; } case 5: { clrscr(); printf("BFS result:\\n"); BFS(g); break; } case 6: exit(0); } } } main creatgraph displaygraph BFS DFS BFSsearch DFSsearch initqueue dequeue enqueue 四、调试分析 ⒈本来想将图的顶点元素的类型定义为字符型的，但是在运行的时候发现在输入顶点数和弧 数后，总是会在有字符没有输入就直接运行下一个语句了，改变了很多的方法，最后只 有将顶点的类型定义为才解决了上述的问题。 ⒉在写程序的时候，开始creatgraph函数的部分代码为 for(i=0;i scanf("%d g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } g.vexnum=n; g.arcnum=e; 总是会有这样的提示“可能在‘g’定义以前已经使用了在creatgraph函数中”，经过多 次的调试，最后代码改为 g.vexnum=n; g.arcnum=e; for(i=0;i scanf("%d g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } 就解决了问题，但是我还是不清楚原因。 3.在编写BFSsearch函数的时候，用指针入队还是用下标值入队，由于对指针的掌握不够， 最后选择了比较容易的用下标值作为队列的类型int。 4.在调试的时候，选择选项3、4、5的时候总是没有执行printf语句，最后分别在主函数和要调用的函数中都加上同一printf语句就解决了问题，能够显示printf中的信息。 5. 算法的时空分析 各操作的算法时间复杂度比较合理 initqueue，emptyqueue，enqueue，dequeue，visit为O(1)；creatgraph ，displaygraph1，displaygraph2BFSsearch，DFS，DFSsearch，BFS为O(n), 注：n为图的顶点数。 6.本次实验采用数据抽象的程序设计方法，将程序化为三层次结构，设计时思路清晰，使调 试也较顺利，各模块有较好的可重用性。 五、用户手册 ⒈本程序的运行环境为windows xp操作系统，并且在TC2.0中运行，执行文件为Exp8.c； ⒉.在输入有向图的信息的时候，注意输入的顺序，这关系到顶点的位置，否则就会与你想 要的图就不一样了。如你的图为 18 22 20 21 若你输入的顶点的顺序是20,18 ，21，22则它们对应的数值的下标为0,1,2，3。因此表示的弧（起点，终点）就应该为（0,2），（1,0），（2,1），（3,0），（3,2），但是弧输入的顺序没有要求。而创建无向图的时候就没有这个要求了，只要输入能表示该边的两个正确的端点即可。 3.按任意键进入主菜单如图： 注：1：表示创建一个有向图； 2：表示创建一个无向图； 3：表示输出已创建的图； 4：表示深度优先遍历已有的图； 5：表示广度优先遍历已有的图； 6：表示退出程序状态。 4. 进入演示程序后，完成编译，再点击超级工具集里的中文DOS环境运行选项，进入DOS 环境中，用户根据需求键入相应的数据，可以看到相应的结果。 六、测试结果 若想创建一个无向图（在主菜单选择2）： 56 57 10 18 19 11 12 20 13 则在主菜单选择2输入的图如图所示： 按任意键进入主菜单选择3，输出图为： 按任意键进入主菜单选择4，输出DFS的结果： 按任意键进入主菜单选择5，输出BFS的结果: 按任意键进入主菜单选择6，退出程序。 七、附录：源程序 #include #include #include #include #include #define NULL 0#define FALSE 0 #define TURE 1 #define maxsize 100 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; /*创建一个空队列*/ 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 full！！！\\n"); else { q.elem[q.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.elem[q.front]; q.front=(q.front+1)%maxsize; return cur; } } /*判断队列是否为空*/ int emptyqueue(struct queue q) { if(q.front==q.rear) return 1; else return 0; } /*创建有向图*/ struct graph creatgraph1() { 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 g.vexnum=n; g.arcnum=e; for(i=0;i scanf("%d g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i scanf("%d%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; } /*创建无向图*/ struct graph creatgraph2() { int e,i,s,d; int a; struct graph g; struct arcnode *p,*q; printf("the number of vex(n) and arc(e):"); scanf("%d%d g.vexnum=n; g.arcnum=e; for(i=0;i scanf("%d g.vexpex[i].data=a; g.vexpex[i].firstarc=NULL; } for(i=0;i scanf("%d%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; q=(struct arcnode *)malloc(sizeof(struct arcnode)); q->adjvex=s; q->info=g.vexpex[s].data; q->nextarc=g.vexpex[d].firstarc; g.vexpex[d].firstarc=q; } return g; } /*显示图*/ void displaygraph(struct graph g,int n) { int i; struct arcnode *p; printf("diaplay the graph;\\n"); for(i=0;i p=g.vexpex[i].firstarc; while(p!=NULL) { printf("(%d,%d)-> p=p->nextarc; } printf("^\\n"); } } /*连通图广度优先遍历*/ void BFSsearch(struct graph g,int v) { int i; struct arcnode *p; Q=initqueue();printf("%5d 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 visit[p->adjvex]=TURE; } p=p->nextarc; } } } /*非连通图广度优先遍历*/ void BFS(struct graph g) { int i; printf("BFS result:\\n"); for(i=0;i for(i=0;i BFSsearch(g,i); printf("\\n\\n"); } /*连通图深度优先遍历*/ void DFSsearch(struct graph g,int v) { struct arcnode *p; printf("%5d p=g.vexpex[v].firstarc; while(p!=NULL) { if(!visit[p->adjvex]) DFSsearch(g,p->adjvex); p=p->nextarc; } } void DFS(struct graph g) /*非连通图深度优先遍历*/ { int i; printf("DFS result:\\n"); for(i=0;i for(i=0;i printf("\\n\\n"); } int menu_select() /*主菜单定义*/ { char s[80]; int c; gotoxy(1,25); /*将光标定在第25行第1列*/ printf("press any key enter menu ......\\n"); /*提示按任意键继续*/ getch(); /*读入任意字符*/ clrscr(); /*清屏*/ gotoxy(1,1); printf("***************MENU***************\\n\\n"); printf(" 1. Make a digraph by youself!\\n"); printf(" 2. Make a undigraph by youself!\\n"); printf(" 3. Ontput your graph!\\n"); printf(" 4. Depth_first search your graph!\\n"); printf(" 5. Bredth_first search your graph!\\n"); printf(" 6. Quit!\\n"); printf("**********************************\\n"); do{ printf("\\n Enter you choice (1~6):\\n"); /*提示输入选项*/ scanf("%s c=atoi(s); /*将输入的字符串转化为整型*/ }while(c<1||c>6); return c; } /*主函数*/ void main() { struct graph g; int i; clrscr(); /*清屏*/ for(;;) { switch(menu_select()) { case 1: { clrscr(); g=creatgraph1(); break; } case 2: { clrscr(); g=creatgraph2(); break; } case 3: { clrscr(); printf("diaplay the graph;\\n"); displaygraph(g,n); break; } case 4: { clrscr(); printf("DFS result:\\n"); DFS(g); break; } case 5: { clrscr(); printf("BFS result:\\n"); BFS(g); break; } case 6: exit(0); } } }下载本文
