2022年实现深度优先搜索和广度优先搜索算法参照 .pdf

《2022年实现深度优先搜索和广度优先搜索算法参照 .pdf》由会员分享，可在线阅读，更多相关《2022年实现深度优先搜索和广度优先搜索算法参照 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

3、图的创建过程中暂不支持重复验证，名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 10 页 -因此不能对一条边进行重复定义*/#include#include#include#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex;struct ArcNode*nextarc;/InfoType*info;ArcNode;/*链表结点的结构用于创建栈或是队列*/typedef struct LinkNode ArcNode*parc;/存储指针地址struct LinkNode*next;/指向一下个结点LinkNode

4、;typedef struct VNode char cData;/顶点元素值ArcNode*firstarc;/指向第一条依附于该点的边VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices;int vexnum;/图的当前顶点数和弧数int arcnum;ALGraph;int VisitedMAX_VERTEX_NUM;/*将生成的图打印出来以便确认正确性*/int PrintCheck(ALGraph*pag)int i;ArcNode*p;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 10 页 -prin

5、tf(nCheck the Graph!n);printf(Notdatatnexttnextt.n);for(i=0;ivexnum;i+)printf(%dt%ct,i,pag-verticesi.cData);p=pag-verticesi.firstarc;while(p)printf(%dt,p-adjvex);p=p-nextarc;printf(n);return 1;/*采用前插法创建邻接表*/int CreateGraph(ALGraph*pag,int start,int end)ArcNode*arcNodes=(ArcNode*)malloc(sizeof(ArcNod

6、e);ArcNode*arcNodee=(ArcNode*)malloc(sizeof(ArcNode);ArcNode*p;if(!arcNodes|!arcNodee)return 0;/从 start-end生成关系arcNodes-adjvex=end;/下一结点的位置p=pag-verticesstart.firstarc;if(!p)/第一个结点单独构造 arcNodes-nextarc=pag-verticesstart.firstarc;pag-verticesstart.firstarc=arcNodes;else while(p-nextarc)p=p-nextarc;p-

7、nextarc=arcNodes;arcNodes-nextarc=NULL;/end-start 的关系生成arcNodee-adjvex=start;/下一结点的位置p=pag-verticesend.firstarc;名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 10 页 -if(!p)/第一个结点单独构造 arcNodee-nextarc=pag-verticesend.firstarc;pag-verticesend.firstarc=arcNodee;else while(p-nextarc)p=p-nextarc;p-nextarc=arcNodee;arcNod

8、ee-nextarc=NULL;return 1;/*深度优先遍历,非递归方式*结点先访问再入栈*栈的存储结构直接采用了LinkNode 构成的链表*采用前插法进行插入与删除，从而也可以完成栈的功能*栈空条件 Stack-next=NULL*/void DFSTraverse(ALGraph ag,int start)LinkNode*Stack=(LinkNode*)malloc(sizeof(LinkNode);/链表头结点，用做栈LinkNode*pStack=(LinkNode*)malloc(sizeof(LinkNode);/对栈操作的指针LinkNode*temp;/临时存储Ar

9、cNode*p;int i;if(!pStack|!Stack)return;Stack-next=NULL;p=ag.verticesstart.firstarc;Visitedstart=1;/Flag printf(n输出深度优先遍历顺序:);printf(%c,ag.verticesstart.cData);/访问第一个点while(1)/正常情况下执行一次，为了打印孤立结点/push stack pStack-parc=p;pStack-next=Stack-next;/将 p 接入链式栈中Stack-next=pStack;/push over 名师资料总结-精品资料欢迎下载-名师

10、精心整理-第 4 页，共 10 页 -while(p&(Stack-next)/当并且栈不为空时 while(p)if(Visitedp-adjvex)p=p-nextarc;else Visitedp-adjvex=1;printf(%c,ag.verticesp-adjvex.cData);/Visit Function/push stack pStack=(LinkNode*)malloc(sizeof(LinkNode);if(!pStack)return;/结点建立不成功pStack-parc=p;pStack-next=Stack-next;Stack-next=pStack;/p

11、ush over p=ag.verticesp-adjvex.firstarc;/pop stack temp=Stack-next;Stack-next=temp-next;p=temp-parc-nextarc;free(temp);/pop over for(i=0;inext=NULL*/void BFSTraverse(ALGraph ag,int start)LinkNode*Queue=(LinkNode*)malloc(sizeof(LinkNode);/链表头结点，用做队列LinkNode*pQueue=(LinkNode*)malloc(sizeof(LinkNode);/

12、对队列操作的指针LinkNode*temp;/临时存储LinkNode*last;/指向最后一个元素的指针ArcNode*p;int i;if(!Queue|!pQueue)return;printf(n输出广度优先遍历次序:);printf(%c,ag.verticesstart.cData);p=ag.verticesstart.firstarc;Visitedstart=1;while(1)/正常情况下执行一次循环/EnQueue pQueue-parc=p;Queue-next=pQueue;pQueue-next=NULL;last=pQueue;/指向最后一个元素的指针/EnQue

13、ue over while(p&Queue-next)while(p)if(!Visitedp-adjvex)Visitedp-adjvex=1;printf(%c,ag.verticesp-adjvex.cData);/Visit Function/EnQueue pQueue=(LinkNode*)malloc(sizeof(LinkNode);if(!pQueue)return;pQueue-parc=p;pQueue-next=NULL;last-next=pQueue;last=last-next;/指向最后一个元素的指针名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共

14、10 页 -/EnQueue over p=p-nextarc;/DeQueue temp=Queue-next;p=ag.verticestemp-parc-adjvex.firstarc;Queue-next=temp-next;/DeQueue over for(i=0;iag.vexnum;i+)/打印出孤立点 if(!Visitedi)printf(%c,ag.verticesi.cData);p=ag.verticesi.firstarc;if(i=ag.vexnum)break;printf(nn);/*主函数负责对图的初始化工作*其中包括图的结点初始化，边初始化*其中大部分的

15、while(1)语句用于验证输入数据的有效性*/void main()ALGraph ag;int i,n,m;int choose;/选择遍历结点int start,end;/边的起点与终点的位置printf(说明:采用邻接表的存储结构，生成无向图n 输入数据请回车确认nn);while(1)/结点个数有效性验证 printf(请输入图的结点个数,并回车:);scanf(%d,&n);if(n0)break;else printf(n请注意结点个数不能大于20,并且不能为 0!n);ag.vexnum=n;名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 10 页 -printf

16、(n初始化图的结点，输入字符并回车:n);for(i=0;iag.vexnum;i+)/图的结点数据 printf(No.%d=,i);fflush(stdin);scanf(%c,&ag.verticesi.cData);ag.verticesi.firstarc=NULL;m=(n-2)*(n+1)/2+1;/顶点数为 n 的图最多的边的数量为m while(1)/边的数量有效性验证 printf(请输入边的数量:);fflush(stdin);scanf(%d,&i);if(i=0)break;else printf(n请注意边的数量不能大于%d,并且不能小于 1!n,m);ag.arc

17、num=i;printf(n初始化图的边，结点从0 开始计，最大为%dn,n-1);for(i=1;i=ag.arcnum;i+)while(1)/起点有效性验证 printf(第 条边的起点:,i);fflush(stdin);scanf(%d,&start);if(start=0)break;else printf(重新输入 );while(1)/终点有效性验证 printf(第 条边的终点:,i);fflush(stdin);scanf(%d,&end);if(end=0&end!=start)break;else printf(重新输入 );名师资料总结-精品资料欢迎下载-名师精心整理

18、-第 8 页，共 10 页 -printf(n);CreateGraph(&ag,start,end);PrintCheck(&ag);/打印出生成的图printf(n开始进行图的遍历!n);while(1)/起始点有效性验证 printf(请输入深度优先遍历的开始结点:);fflush(stdin);scanf(%d,&choose);if(choose=0&choose=0&choosen)break;else printf(重新输入 );BFSTraverse(ag,choose);/广度优先遍历system(pause);程序运行截图名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 10 页 -六、实验体会相对于第二个实验，实验三实现深度优先搜索和广度优先搜索算法的难度大了许多，对理论课基础的要求比较高，图这种数据结构是我的薄弱之处，隐刺刚开始我就感觉到无处下手，在请教同学后，慢慢地深入，才一步步的把这个问题解决，在之后更要多加练习，巩固这方面的知识。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 10 页 -