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

《数据结构实验报告 DFS和BFS算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、tdlib.h>#defineMax20intvisited[Max];structqueue//队列的结构体{int*head;//指向所申请得到的空间的首地址int*front;//头指针，若队列不为空，指向队列头元素int*rear;//尾指针，若队列不空，指向队列尾元素的下一个位置intstacksize;//当前已分配的存储空间}s;//------------图的数组存储表示-------------structMgraph{charvexs[Max];intarcs[Max][Ma

4、x];intvexnum,arcnum;}G;intLocatevex(charv)//确定v在G中的位置{inti,t;for(i=0;i

5、sh(stdin);printf("请输入%d个顶点",G.vexnum);for(i=0;i

6、d:",k);scanf("%c,%c",&v1,&v2);fflush(stdin);i=Locatevex(v1);j=Locatevex(v2);G.arcs[i][j]=1;G.arcs[j][i]=1;}}//--------------返回v的第一个邻接顶点-------------------intFirstadjvex(intv){inti;for(i=0;i

7、----------返回v的(相对于w的）下一个邻接顶点----------------------intNextadjvex(intv,intw){inti;for(i=0;iw)return(i);i=-1;return(i);}//--------从第v个顶点出发递归地深度优先遍历图G---------------voidDFS(intv){intw;visited[v]=1;printf("%c",G.vexs[v]

8、);for(w=Firstadjvex(v);w>=0;w=Nextadjvex(v,w))if(!visited[w])DFS(w);}//-----------------对图G作深度优先遍历--------------voidDfstraverse(){inti;for(i=0;i