实现深度优先搜索与广度优先搜索算法.doc

实 验 报 告课程名称 数据结构实验 实验项目 实现深度优先搜索与广度优先搜索算法 专业班级 计算机科学与技术1班 姓 名全永春 学 号 2011314103 指导教师 成 绩 日 期 一、目的与要求1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历。 2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。 二、实验内容 1、建立图的几种存储方式2、图的深度优先搜索算法3、图的广度优先搜索算法三、实验原理 图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。 四、实验步骤1建立图的存储结构。2输入图的基本接点与信息，完成初始化图的工作。3完成图的深度优先搜索（DFS）和广度优先搜索算法，可以采用菜单形式进行显示与选择。（可以在键盘输入边的信息以构建一个无向图。以（a,b）的形式输入边的信息；对此无向图进行深度优先搜索，并输出正确的序列。）#include#include#define max 20typedef int Date ;typedef char Info ;typedef struct bian/边的数据结构int zhi;/Info info;struct bian * N;bian;typedef struct /节点数据结构int i ;bian *F;Vex;typedef struct /用来作队列，栈int top;int button;int a100;S;S s;Vex vmax+1;/节点个数bian *bu;int n,e;void create()/创建图 bian *b;int i,v1,v2;void memo();printf(请输入节点个数N，边数En);printf( 节点个数Nn);printf( );scanf(%d,&n);printf( 边数En);printf( );scanf(%d,&e);printf(请输入节点信息n);for(i=1;i=n;i+)scanf(%d,&vi.i);for(i=1;i=n;i+)vi.F=0;printf(请输入边n);printf( 起点 终点 n);for(i=1;izhi=v2;b-N=vv1.F;vv1.F=b;b=(bian *)malloc(sizeof(bian);b-zhi=v1;b-N=vv2.F;vv2.F=b;memo();int pmax;void vist(int i)printf(%d ,vi.i);printf(- );void aa()/查看表结构void memo();int i,j;bian* b;printf( num DAte next next next .n );for(i=1;izhi;printf(%d ,vj.i);b=b-N;printf(n);printf(n);memo();int f(int i)/返回没有被访问过的I的节点int j=0;bu=vi.F;while(bu!=0)if(pbu-zhi=0)j=bu-zhi;break; bu=bu-N;return j;void dfst(int i)/深度优先搜索int j,t;if(pi=0)vist(i);pi=1;s.a+s.top=i;while(s.top!=0)t=s.as.top;j=f(t);if(j!=0)dfst(j);else s.top=s.top-1;void ss()void memo();int i,j;s.top=0;for(i=1;i=n;i+)pi=0;printf(请输入搜索起点in);scanf(%d,&i);printf(遍历次序：);for(;i=n;i+)if(pi=0)dfst(i);for(i=1;izhi;bu=bu-N;if(pj=0)fst(j);void wfst()void memo();int j,i;s.button=s.top=0;for(i=1;i=n;i+)pi=0;printf(请输入搜索起点in);scanf(%d,&i);printf(遍历次序：);for(;i0)fst(j);elses.button=s.button+1;for(i=1;i0)fst(j);elses.button=s.button+1;printf(n);memo();void memo()/菜单显示int i;printf(1.创建无向图 2.深度优先搜索 3.广度优先搜索 4.查看邻接表逻辑结构 5.退出n);printf(请输入相应数字选择所需操作n);scanf(%d,&i);switch(i)case 1:create();break;case 2:ss();break;case 3:wfst();break;case 4:aa();break;case 5: exit(1);break;void main()memo();五、运行结果六、实验体会这堂Huffman编码以及解码的数据结构实验课让我对数据结构的整体学习有了进一步的了解，刚开始的时候稍微有点迷茫，但是循序渐进，一点点了解了这堂课的内容，经历过不少错误之后，到最后熟悉二叉树、Huffman树的基本概念，掌握二叉