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

《实现深度优先搜索与广度优先搜索算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告课程名称数据结构实验实验项目实现深度优先搜索与广度优先搜索算法专业班级计算机科学与技术1班姓名全永春学号2011314103指导教师成绩日期一、目的与要求1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历。2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容1、建立图的几种存储方式2、图的深度优先搜索算法3、图的广度优先搜索算法三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历。广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向

2、下一层搜索；而深度优先遍历是将某一条枝桠上的所有节点都搜索到了之后，才转向搜索另一条枝桠上的所有节点。四、实验步骤1．建立图的存储结构。2．输入图的基本接点与信息，完成初始化图的工作。3．完成图的深度优先搜索（DFS）和广度优先搜索算法，可以采用菜单形式进行显示与选择。（可以在键盘输入边的信息以构建一个无向图。以（a,b）的形式输入边的信息；对此无向图进行深度优先搜索，并输出正确的序列。）#include#include#definemax20typedefintDate;typedefcharInfo;12typedefstructbian//边的

3、数据结构{intzhi;//Infoinfo;structbian*N;}bian;typedefstruct//节点数据结构{inti;bian*F;}Vex;typedefstruct//用来作队列，栈{inttop;intbutton;inta[100];}S;Ss;Vexv[max+1];//节点个数bian*bu;intn,e;voidcreate()//创建图{bian*b;inti,v1,v2;voidmemo();printf("请输入节点个数N，边数E");printf("节点个数N");printf("");scanf("%d",&n);12printf("边

4、数E");printf("");scanf("%d",&e);printf("请输入节点信息");for(i=1;i<=n;i++){scanf("%d",&v[i].i);}for(i=1;i<=n;i++)v[i].F=0;printf("请输入边");printf("起点终点");for(i=1;i<=e;i++){printf("");scanf("%d%d",&v1,&v2);b=(bian*)malloc(sizeof(bian));b->zhi=v2;b->N=v[v1].F;v[v1].F=b;b=(bian*)malloc(sizeof(bian));b

5、->zhi=v1;b->N=v[v2].F;v[v2].F=b;12}memo();}intp[max];voidvist(inti){printf("%d",v[i].i);printf("->");}voidaa()//查看表结构{voidmemo();inti,j;bian*b;printf("numDAtenextnextnext....");for(i=1;i<=n;i++){printf("%d",i);printf("%d",v[i].i);b=v[i].F;while(b!=0){j=b->zhi;printf("%d",v[j].i);b=b->N;}12print

6、f("");}printf("");memo();}intf(inti)//返回没有被访问过的I的节点{intj=0;bu=v[i].F;while(bu!=0){if(p[bu->zhi]==0){j=bu->zhi;break;}bu=bu->N;}returnj;}voiddfst(inti)//深度优先搜索{intj,t;if(p[i]==0){vist(i);p[i]=1;s.a[++s.top]=i;}12while(s.top!=0){t=s.a[s.top];j=f(t);if(j!=0)dfst(j);elses.top=s.top-1;}}voidss(){v

7、oidmemo();inti,j;s.top=0;for(i=1;i<=n;i++)p[i]=0;printf("请输入搜索起点i");scanf("%d",&i);printf("遍历次序：");for(;i<=n;i++){if(p[i]==0){dfst(i);}12}for(i=1;i<=n;i++){if(p[i]==0)dfst(i);}printf("");memo();}//广度优先搜索fst(inti){i