数据结构实验报告DFS和BFS算法_第1页
数据结构实验报告DFS和BFS算法_第2页
数据结构实验报告DFS和BFS算法_第3页
数据结构实验报告DFS和BFS算法_第4页
数据结构实验报告DFS和BFS算法_第5页
已阅读5页,还剩2页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论