数据结构实验报告(三)：实现深度优先搜索与广度优先搜索算法

《数据结构实验报告(三)：实现深度优先搜索与广度优先搜索算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、佛山科学技术学院实验报告课程名称数据结构实验项目实现深度优先搜索与广度优先搜索算法专业班级10网络工程2姓名张珂卿学号2010394212指导教师成绩日期2011年11月16日一、实验目的1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历；2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。二、实验内容1、建立图的存储方式；2、图的深度优先搜索算法；3、图的广度优先搜索算法。 三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历

2、；深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点；广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。四、实验步骤1．建立图的存储结构；2．输入图的基本接点与信息，初始化图；3．编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序；4.采用菜单形式进行显示与选择。5.测试数据和结果显示（1）从键盘输入顶点数和边数；（2）输入顶点信息；（3）输入边的信息，以（a,b）的形式输入边的信息，构

3、建一个无向图；（4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。五、程序源代码及注释/********************************采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复验证，因此不能对一条边进行重复定义******************************/#include#include#include#defineMAX_VERTEX_NUM20typedefstructArcNode{i

4、ntadjvex;structArcNode*nextarc;//InfoType*info;}ArcNode;/**********************************链表结点的结构用于创建栈或是队列********************************/typedefstructLinkNode{ArcNode*parc;//存储指针地址structLinkNode*next;//指向一下个结点}LinkNode;typedefstructVNode{charcData;//顶点元素值Ar

5、cNode*firstarc;//指向第一条依附于该点的边}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices;intvexnum;//图的当前顶点数和弧数intarcnum;}ALGraph;intVisited[MAX_VERTEX_NUM];/**********************************将生成的图打印出来以便确认正确性********************************/intPrintCheck(ALGr

6、aph*pag){inti;ArcNode*p;printf("ChecktheGraph!");printf("Notdatatnexttnextt.....");for(i=0;ivexnum;i++){printf("%dt%ct",i,pag->vertices[i].cData);p=pag->vertices[i].firstarc;while(p){printf("%dt",p->adjvex);p=p->nextarc;}printf("");}return

7、1;}/***************************采用前插法创建邻接表*************************/intCreateGraph(ALGraph*pag,intstart,intend){ArcNode*arcNodes=(ArcNode*)malloc(sizeof(ArcNode));ArcNode*arcNodee=(ArcNode*)malloc(sizeof(ArcNode));ArcNode*p;if(!arcNodes

8、

9、!arcNodee)return0;//从st

10、art->end生成关系arcNodes->adjvex=end;//下一结点的位置p=pag->vertices[start].firstarc;if(!p)//第一个结点单独构造{arcNodes->nextarc=pag->vertices[start].firstarc;pag->vertices[start].firstarc=arcNodes;}