数据结构实验报告DFS和BFS算法

1、（规格为a4纸或a3纸折叠）佛山科学技术学院（用四号宋体）实 验 报 告（用小二号黑体）课程名称 数据结构实验 实验项目 实现dfs和bfs算法 专业班级 姓 名 学 号 指导教师 成 绩 日 期 （用小四号宋体） 一、目的与要求1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历。 2、掌握图的深度优先搜索（dfs）与广度优先搜索（bfs）算法。二、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优

2、先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。三、实验步骤1建立图的存储结构。2输入图的基本接点与信息，完成初始化图的工作。3完成图的深度优先搜索（dfs）和广度优先搜索算法，可以采用菜单形式进行显示与选择。（可以在键盘输入边的信息以构建一个无向图。以（a,b）的形式输入边的信息；对此无向图进行深度优先搜索，并输出正确的序列。）4、 源代码#include #include #define max 20int visitedmax;struct queue/队列的结构体int *head;/指向所申请得到的空间的首地址int *front;/头指针，若队列不

3、为空，指向队列头元素int *rear;/尾指针，若队列不空，指向队列尾元素的下一个位置int stacksize;/当前已分配的存储空间s;/-图的数组存储表示-struct mgraphchar vexsmax;int arcsmaxmax;int vexnum,arcnum;g;int locatevex(char v)/确定v在g中的位置int i,t;for(i=0;ig.vexnum;i+)if(g.vexsi=v) t=i;return(t);/-采用数组表示法，构造无向图g-void createudg()int i,j,k;char v1,v2;printf(请输入顶点数和弧

4、数：);scanf(%d,%d,&g.vexnum,&g.arcnum);fflush(stdin);printf(请输入%d个顶点n,g.vexnum);for(i=0;ig.vexnum;i+)printf(请输入顶点%d: ,i);scanf(%c,&g.vexsi);fflush(stdin);for(i=0;ig.vexnum;i+)for(j=0;jg.vexnum;j+) g.arcsij=0;printf(请输入%d条弧n,g.arcnum);for(k=0;kg.arcnum;k+)printf(请输入弧%d: ,k);scanf(%c,%c,&v1,&v2);fflush(

5、stdin);i=locatevex(v1);j=locatevex(v2);g.arcsij=1;g.arcsji=1;/-返回v的第一个邻接顶点-int firstadjvex(int v)int i; for(i=0;ig.vexnum;i+)if(g.arcsvi=1) return(i);i=-1;return(i);/-返回v的(相对于w的）下一个邻接顶点-int nextadjvex(int v,int w)int i;for(i=0;iw) return(i);i=-1;return(i);/-从第v个顶点出发递归地深度优先遍历图g-void dfs(int v) int w;

6、visitedv=1;printf(%c ,g.vexsv);for(w=firstadjvex(v);w=0;w=nextadjvex(v,w)if(!visitedw) dfs(w);/-对图g作深度优先遍历-void dfstraverse()int i;for(i=0;ig.vexnum;i+) visitedi=0;printf(深度优先遍历：);for(i=0;i=s.stacksize)/队列满，追加存储空间s.head=(int *)realloc(s.head,(s.stacksize+10)*sizeof(int);if(!s.head) exit(0);/存储分配失败s.

7、stacksize+=10;*s.rear=e;s.rear+=1;void dequeue(int u)/若队列不空，则删除s的队头元素u=*s.front;s.front+=1;/-按广度优先非递归遍历图g-void bfstraverse()int v,u=0,w;for(v=0;vg.vexnum;v+) visitedv=0;initqueue();printf(广度优先遍历：);for(v=0;v=0;w=nextadjvex(u,w)if(!visitedw)visitedw=1;printf(%c ,g.vexsw);enqueue(w);printf(n);void main

8、()int i; printf（*n);printf(1.创图n2.深度优先搜索n3.广度优先搜索n4.退出n); printf(*n);printf(请选择要操作的选项：);scanf(%d,&i);switch(i) case 1:createudg();break;case 2:dfstraverse();break;case 3:bfstraverse();break;case 4:exit(0);main();5、 实验结果6、 思考题1图的存储方式有几种？本实验中你会采用什么样的存储方式？答：图的存储方式有数组表示法、邻接表、十字链表、邻接多重表等4种常用存储方式。本实验中我采用了

9、数组表示法存储。 2、给出一幅无向图g如下：v(g)=v1，v2，v3，v4，v5，v6，v7，v8 ，e(g)=(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)，（v1,v8），（v2,v8）1）请画出示意图；2）请根据你采用的存储方式画出存储图示； 3）在题目2的基础上，请给出图的深度优先搜索序列；v1v4v24）在题目2的基础上，请给出图的广度优先搜索序列。v6 解：（1）v7v3v8v50 1 2 3 4 5 6 70 1 1 0 0 0 0 11 0 0 1 1 0 0 11 0 0 0 0 1 1 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 1 0 0 0 0 01 1 0 0 0 0 0 001234567 v1 v2 v3 v4 v5 v6 v7 v8 (2) (3)深度优先搜索序列：a b d e h c f g (4)广度优先搜索序列：a b c