佛山科学技术学院实验报告课程名称数据结构实验项目实现深度优先搜索与广度优先搜索算法专业班级 10网络工程2 姓名张珂卿学号 2010394212指导教师成绩日期 2011年11月16日一、实验目的1、通过本实验，掌握图，无向图的基本概念，掌握图的遍历；2、掌握图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。
二、实验内容1、建立图的存储方式；2、图的深度优先搜索算法；3、图的广度优先搜索算法。
三、实验原理图的遍历是图的算法中一种非常重要的算法，通过建立图的存储结构，采用深度优先搜索与广度优先搜索算法可以进行图的遍历；深度优先遍历是树的先根遍历的推广，是将某一条枝上的所有节点都搜索到了之后，才转向搜索另一条枝上的所有节点；广度优先遍历与深度优先遍历的区别在于：广度优先遍历是以层为顺序，将某一层上的所有节点都搜索到了之后才向下一层搜索。
四、实验步骤1．建立图的存储结构；2．输入图的基本接点与信息，初始化图；3．编写图的深度优先搜索（DFS）和广度优先搜索算法（BFS）程序；4.采用菜单形式进行显示与选择。
5.测试数据和结果显示（1）从键盘输入顶点数和边数；（2）输入顶点信息；（3）输入边的信息，以（a,b）的形式输入边的信息，构建一个无向图；（4）对此无向图进行深度优先搜索和广度优先搜索，并输出正确的序列。
五、程序源代码及注释/********************************采用邻接表的存储结构*构建无向图*图的创建过程中暂不支持重复验证，因此不能对一条边进行重复定义******************************/#include<stdio.h>#include<malloc.h>#include<windows.h>#define MAX_VERTEX_NUM 20typedef struct ArcNode{int adjvex;struct ArcNode* nextarc;//InfoType* info;}ArcNode;/**********************************链表结点的结构用于创建栈或是队列********************************/typedef struct LinkNode{ArcNode* parc; //存储指针地址struct LinkNode* next; //指向一下个结点}LinkNode;typedef struct VNode{char cData; //顶点元素值ArcNode* firstarc; //指向第一条依附于该点的边}VNode,AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum; //图的当前顶点数和弧数int arcnum;}ALGraph;int Visited[MAX_VERTEX_NUM];/**********************************将生成的图打印出来以便确认正确性********************************/int PrintCheck(ALGraph* pag){int i;ArcNode* p;printf("\nCheck the Graph!\n");printf("No\tdata\tnext\tnext\t.....\n");for(i=0; i<pag->vexnum; i++){printf("%d\t%c\t",i,pag->vertices[i].cData);p = pag->vertices[i].firstarc;while(p){printf("%d\t",p->adjvex);p = p->nextarc;}printf("\n");}return 1;}/***************************采用前插法创建邻接表*************************/int CreateGraph(ALGraph* pag,int start,int end){ArcNode* arcNodes = (ArcNode*)malloc(sizeof(ArcNode));ArcNode* arcNodee = (ArcNode*)malloc(sizeof(ArcNode));ArcNode* p;if(!arcNodes || !arcNodee) return 0;//从start->end生成关系arcNodes->adjvex = end; //下一结点的位置p = pag->vertices[start].firstarc;if(!p) //第一个结点单独构造{arcNodes->nextarc = pag->vertices[start].firstarc;pag->vertices[start].firstarc = arcNodes;}else{while(p->nextarc) p = p->nextarc;p->nextarc = arcNodes;arcNodes->nextarc = NULL;}//end->start 的关系生成arcNodee->adjvex = start; //下一结点的位置p = pag->vertices[end].firstarc;if(!p) //第一个结点单独构造{arcNodee->nextarc = pag->vertices[end].firstarc;pag->vertices[end].firstarc = arcNodee;}else{while(p->nextarc) p = p->nextarc;p->nextarc = arcNodee;arcNodee->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; //临时存储ArcNode* p;int i;if(!pStack||!Stack) return;Stack->next = NULL;p = ag.vertices[start].firstarc;Visited[start]=1; //Flagprintf("\n输出深度优先遍历顺序:");printf(" %c ",ag.vertices[start].cData); //访问第一个点while(1) //正常情况下执行一次，为了打印孤立结点{//push stackpStack->parc = p;pStack->next = Stack->next; //将p接入链式栈中Stack->next = pStack;//push overwhile(p && (Stack->next)) //当并且栈不为空时{while(p){if(Visited[p->adjvex]) p = p->nextarc;else{Visited[p->adjvex]=1;printf(" %c ",ag.vertices[p->adjvex].cData); //Visit Function//push stackpStack = (LinkNode*)malloc(sizeof(LinkNode));if(!pStack) return; //结点建立不成功pStack->parc = p;pStack->next = Stack->next;Stack->next = pStack;//push overp = ag.vertices[p->adjvex].firstarc;}}//pop stacktemp = Stack->next;Stack->next = temp->next;p = temp->parc->nextarc;free(temp);//pop over}for(i=0; i<ag.vexnum; i++) //打印出孤立点{if(!Visited[i]) printf(" %c ",ag.vertices[i].cData);p = ag.vertices[i].firstarc;}if(i = ag.vexnum) break;}printf("\n\n");};/*****************************************广度优先遍历,非递归方式*队列的存储结构直接采用了LinkNode构成的链表*采用后接法进行插入，并用前插法进行删除*从而完成队列的功能，队空条件Queue->next == NULL***************************************/void BFSTraverse(ALGraph ag,int start){LinkNode* Queue = (LinkNode*)malloc(sizeof(LinkNode)); //链表头结点，用做队列LinkNode* pQueue = (LinkNode*)malloc(sizeof(LinkNode)); //对队列操作的指针LinkNode* temp; //临时存储LinkNode* last; //指向最后一个元素的指针ArcNode* p;int i;if(!Queue || !pQueue) return;printf("\n输出广度优先遍历次序:");printf(" %c ",ag.vertices[start].cData);p = ag.vertices[start].firstarc;Visited[start] = 1;while(1) //正常情况下执行一次循环{//EnQueuepQueue->parc = p;Queue->next = pQueue;pQueue->next = NULL;last = pQueue; //指向最后一个元素的指针//EnQueue overwhile(p && Queue->next){while(p){if(!Visited[p->adjvex]){Visited[p->adjvex] = 1;printf(" %c ",ag.vertices[p->adjvex].cData); //Visit Function//EnQueuepQueue = (LinkNode*)malloc(sizeof(LinkNode));if(!pQueue) return;pQueue->parc = p;pQueue->next = NULL;last->next = pQueue;last = last->next; //指向最后一个元素的指针//EnQueue over}p = p->nextarc;}//DeQueuetemp = Queue->next;p = ag.vertices[temp->parc->adjvex].firstarc;Queue ->next = temp->next;//DeQueue over}for(i=0; i<ag.vexnum; i++) //打印出孤立点{if(!Visited[i]) printf(" %c ",ag.vertices[i].cData);p = ag.vertices[i].firstarc;}if(i = ag.vexnum) break;}printf("\n\n");}/*******************************************主函数负责对图的初始化工作*其中包括图的结点初始化，边初始化*其中大部分的while(1)语句用于验证输入数据的有效性******************************************/void main(){ALGraph ag;int i,n,m;int choose; //选择遍历结点int start,end; //边的起点与终点的位置printf("说明: 采用邻接表的存储结构，生成无向图\n 输入数据请回车确认\n\n");while(1) //结点个数有效性验证{printf("请输入图的结点个数,并回车: ");scanf("%d",&n);if(n<MAX_VERTEX_NUM && n>0) break;else printf("\n请注意结点个数不能大于20,并且不能为0!\n");}ag.vexnum = n;printf("\n初始化图的结点，输入字符并回车:\n");for(i=0; i<ag.vexnum; i++) //图的结点数据{printf("No.%d = ",i);fflush(stdin);scanf("%c",&ag.vertices[i].cData);ag.vertices[i].firstarc = NULL;}m = (n-2)*(n+1)/2+1; //顶点数为n的图最多的边的数量为mwhile(1) //边的数量有效性验证{printf("请输入边的数量: ");fflush(stdin);scanf("%d",&i);if(i<=m && i>=0) break;else printf("\n请注意边的数量不能大于%d,并且不能小于1!\n",m); }ag.arcnum = i;printf("\n初始化图的边，结点从0开始计，最大为%d\n",n-1);for(i=1; i<=ag.arcnum; i++){while(1) //起点有效性验证{printf("第<%d>条边的起点: ",i);fflush(stdin);scanf("%d",&start);if(start<n&&start>=0) break;else printf("重新输入 ");}while(1) //终点有效性验证{printf("第<%d>条边的终点: ",i);fflush(stdin);scanf("%d",&end);if(end<n && end>=0 && end!=start) break;else printf("重新输入 ");}printf("\n");CreateGraph(&ag,start,end);}PrintCheck(&ag); //打印出生成的图printf("\n开始进行图的遍历!\n");while(1) //起始点有效性验证{printf("请输入深度优先遍历的开始结点:");fflush(stdin);scanf("%d",&choose);if(choose>=0 && choose<n) break;else printf("重新输入 ");}DFSTraverse(ag,choose); //深度优先遍历i = 0; //重新初始化Visited数组while(Visited[i]!='\0'){Visited[i] = 0;i++;}while(1) //起始点有效性验证{printf("请输入广度优先遍历的开始结点:");fflush(stdin);scanf("%d",&choose);if(choose>=0 && choose<n) break;else printf("重新输入 ");}BFSTraverse(ag,choose); //广度优先遍历system("pause");}程序运行截图六、实验体会这堂实现深度优先搜索与广度优先搜索算法的数据结构实验课难度明显比第二节课要大许多，刚开始有些丈二摸不着头脑，浪费了不少课上的时间，后来回去才慢慢深入，一点点了解了这堂课的内容，经历过不少错误之后，终于算是掌握了图，无向图的基本概念，掌握图的遍历，还有图的深度优先搜索（DFS）与广度优先搜索（BFS）算法。
启发算法与盲目算法一、盲目搜索对一个图进行搜索意味着按照某种特定的顺序依次访问其顶点。
在所有搜索方式中，广度优先算法和深度优先搜索算法都十分重要，因为它们提供了一套系统地访问图数据结构的方法。
我们着重讲解广度优先搜索算法。
1.深度优先搜索深度优先搜索算法（简称DFS）是一种用于遍历或搜索树或图的算法。
沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
当节点的所在边都己被探寻过，搜索将回溯到发现节点的那条边的起始节点。
这一过程一直进行到已发现从源节点可达的所有节点为止。
由于深度优先搜索不是接下来最短路径算法的基础，因此这里不做拓展。
2.广度优先搜索广度优先搜索算法（简称BFS）又称为宽度优先搜索从起点开始，首先遍历起点周围邻近的点，然后再遍历已经遍历过的点邻近的点，逐步的向外扩散，直到找到终点。
在执行算法的过程中，每个点需要记录达到该点的前一个点的位置—父节点。
这样做之后，一旦到达终点，便可以从终点开始，反过来顺着父节点的顺序找到起点，由此就构成了一条路径。
以上两种算法的不同搜索策略可以通过下面网页查看动图，这是两种相邻节点之间的移动代价相等时用到的算法，图中的边不设权值。
3.Dijkstra算法Dijkstra算法是由计算机科学家Edsger W.Dijkstra在1956年提出的。
考虑这样一种场景，在一些情况下，图形中相邻节点之间的移动代价并不相等。
例如，游戏中的一幅图，既有平地也有山脉，那么游戏中的角色在平地和山脉中移动的速度通常是不相等的。
在Dijkstra算法中，需要计算每一个节点距离起点的总移动代价。
同时，还需要一个优先队列结构。
对于所有待遍历的节点，放入优先队列中会按照代价进行排序。
在算法运行的过程中，每次都从优先队列中选出代价最小的作为下一个遍历的节点。
直到到达终点为止。
对比了不考虑节点移动代价差异的广度优先搜索与考虑移动代价的Dijkstra算法。
可以看出当图形为网格图，并且每个节点之间的移动代价是相等的，那么Dijkstra算法将和广度优先算法变得一样。
深度学习算法原理与优化深度学习（Deep Learning）是机器学习中一种非常热门的算法，它的出现让计算机在图片识别、自然语言处理等领域取得了惊人的进步。
与传统的机器学习相比，深度学习可以处理更为复杂且高维度的数据，因此在大数据时代被广泛应用。
但是，深度学习算法也有其弱点，优化成为了深度学习研究中的核心问题之一。
深度学习算法原理深度学习的核心是人工神经网络，它模拟了人类大脑神经元之间的相互作用。
人工神经网络由多个层级组成，每个层级有多个神经元。
第一个层级所接收的输入为原始数据，每个神经元会对数据进行加权和非线性变换，得出一个输出。
第二个层级的输入则是第一个层级的输出，同样进行加权和非线性变换，得出第二个层级的输出。
以此类推，直到输出层得出最终结果。
深度学习算法的训练过程分为前向传播和反向传播两个过程。
前向传播是指在神经网络中，从输入层到输出层，依次进行加权和非线性变换，得出最终结果的过程。
反向传播是指通过误差反向传递，不断调整每个神经元的权值，最终使得神经网络的输出结果更加接近于目标结果。
深度学习算法优化深度学习算法面临的一个重要问题是过拟合（Overfitting），即模型在训练数据上表现很好，但在测试数据上表现很差。
解决过拟合的方法主要有下面四种。
1.正则化（Regularization）正则化是通过在损失函数中添加正则项来惩罚模型复杂度的方法，从而降低拟合能力过强的风险。
正则化包括L1正则化和L2正则化。
L1正则化将权重参数的绝对值作为正则项，L2正则化将权重参数的平方和作为正则项。
2.数据增强（Data Augmentation）数据增强通过对原始数据进行一系列变换后生成新的数据，从而扩大原始数据集，减少过拟合的风险。
3.早停法（Early Stopping）早停法是指在训练过程中，若验证集误差在一定周期内没有降低，则停止训练，防止过度拟合。
早停法需要对模型的泛化能力进行充分了解，因此在实际应用中需要谨慎使用。
剖析深度优先搜索
吴晓晨
【期刊名称】《天津职业院校联合学报》
【年(卷),期】2017(019)002
【摘要】文章将对马的遍历问题等进行讨论,从一维到二维,以拓展思路、不落俗套,全面领会深度优先搜索,进而掌握这一编程技术.%this article will discuss the horse traversal problem from one dimension to two dimensions to unconventionally expand the thinking and comprehensively understand the depth-first search in order to master the programming technology.【总页数】8页(P104-111)
【作者】吴晓晨
【作者单位】天津现代职业技术学院,天津 300350
【正文语种】中文
【中图分类】TP311
【相关文献】
1.深度优先搜索配合菌群算法的配电网故障恢复重构研究 [J], 邢晓敏;孙奇;张鹏宇;李茂清
2.基于深度优先搜索和灰狼算法的微电网重构 [J], 张青林; 辛小南; 程志平
3.基于深度优先搜索算法的交通流向供需失衡路径辨识 [J], 李衬衬;孙锋;孙猛;李大龙;宋子文
4.代价树深度优先搜索及优化 [J], 刘庆宇
5.基于深度优先搜索的模糊测试用例生成方法 [J], 李毅豪;洪征;林培鸿
因版权原因，仅展示原文概要，查看原文内容请购买。
