深度优先搜索法和广度优先搜索法

数据结构简要说明深度优先搜索法(DFS)和广度优先搜索法(BFS)的不同之处~

一个是类似层序遍历，一个类似先序遍历

1、主体区别
深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件)。
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。
2、算法区别
深度优先搜索是每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。
广度优先搜索是每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱，找到所要找的元素时结束程序。
3、用法
广度优先属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
深度优先即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。

扩展资料：
实际应用
BFS在求解最短路径或者最短步数上有很多的应用，应用最多的是在走迷宫上，单独写代码有点泛化，取来自九度1335闯迷宫一例说明，并给出C++/Java的具体实现。
在一个n*n的矩阵里走，从原点（0,0）开始走到终点（n-1,n-1），只能上下左右4个方向走，只能在给定的矩阵里走，求最短步数。n*n是01矩阵，0代表该格子没有障碍，为1表示有障碍物。
int mazeArr[maxn][maxn]; //表示的是01矩阵int stepArr = {{-1,0},{1,0},{0,-1},{0,1}}; //表示上下左右4个方向，int visit[maxn][maxn]; //表示该点是否被访问过，防止回溯，回溯很耗时。核心代码。基本上所有的BFS问题都可以使用类似的代码来解决。
参考资料来源：百度百科-广度优化
参考资料来源：百度百科-深度优化

深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。在深度优先搜索中，对于最新发现的结点，如果它还有以此为起点而未搜过的边，就沿着边继续搜索下去。当结点v的所有边都已被探寻过，搜索将回溯到发现结点v有那条边的始结点。这一过程一直进行到已发现从源结点可达的所有结点为止。如果还存在未被发现的结点，则选择其中一个作为源结点并重复以上过程，整个过程反复进行直到所有结点都被发现为止。

深度优先搜索基本算法如下{递归算法}：
PROCEDURE dfs_try(i);
FOR i:=1 to maxr DO
BEGIN
IF 子结点 mr 符合条件 THEN
BEGIN
产生的子结点mr入栈；
IF 子结点mr是目标结点
THEN 输出
ELSE dfs_try(i+1);
栈顶元素出栈;
END;
END; 宽度优先搜索算法（又称广度优先搜索算法）是最简单的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijksta单源最短路径算法和Prim最小生成树算法都采用了与宽度优先搜索类似的思想。
宽度优先搜索的核心思想是：从初始结点开始，应用算符生成第一层结点，检查目标结点是否在这些后继结点中，若没有，再用产生式规则将所有第一层的结点逐一扩展，得到第二层结点，并逐一检查第二层结点中是否包含目标结点。若没有，再用算符逐一扩展第二层所有结点……，如此依次扩展，直到发现目标结点为止。

宽度优先搜索基本算法如下：
list[1]:=source; {加入初始结点，list为待扩展结点的表}
head:=0; {队首指针}
foot:=1; {队尾指针}
REPEAT
head:=head+1;
FOR x:=1 to 规则数 DO
BEGIN
根据规则产生新结点nw;
IF not_appear(nw,list) THEN {若新结点队列中不存在，则加到队尾}
BEGIN
foot:=foot+1;
list[foot]:=nw;
list[foot].father:=head;
IF list[foot]=目标结点 THEN 输出；
END；
END；
UNTIL head>foot; {队列为空表明再无结点可扩展}

---

马龙县13776817538： 深度优先搜索和广度优先搜索、A星算法三种算法的区别和联系? - ？
邬屈奥义：[答案] 1、何谓启发式搜索算法 在说它之前先提提状态空间搜索.状态空间搜索,如果按专业点的说法就是将问题求解过程表现为从... 这个寻找的过程就是状态空间搜索. 常用的状态空间搜索有深度优先和广度优先.广度优先是从初始状态一层一层向下找,直...

马龙县13776817538： 深度优先搜索法和广度优先搜索法 - ？
邬屈奥义： 深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图.在深度优先搜索中,对于最新发现的结点,如果它还有以此为起点而未搜过的边,就沿着边继续搜索下去.当结点v的所有边都已被探寻过,搜索将回溯到发现结点v有那条边的始结点....

马龙县13776817538： 数据结构题目,广度优先和深度优先 - ？
邬屈奥义： (一)深度优先搜索的特点是:(1)从上面几个实例看出,可以用深度优先搜索的方法处理的题目是各种 各样的.有的搜索深度是已知和固定的,如例题2-4,2-5,2-6;有的是未知的,如例题2-7、例题2-8;有的搜索深度是有限制的,...

马龙县13776817538： 什么是搜索引擎的深度优先和广度优先 - ？
邬屈奥义： 这是针对搜索引擎蜘蛛抓取策略的两种优先策略: 广度优先:是指网络蜘蛛会先抓取起始网页中链接的所有网页,然后再选择其中的一个链接网页,继续抓取在此网页中链接的所有网页.这是最常用的方式,因为这个方法可以让网络蜘蛛并行处理,提高其抓取速度 深度优先:是指网络蜘蛛会从起始页开始,一个链接一个链接跟踪下去,处理完这条线路之后再转入下一个起始页,继续跟踪链接.这个方法有个优点是网络蜘蛛在设计的时候比较容易.

马龙县13776817538： 数据结构中宽度优先搜索是广度优先还是深度优先搜索. - ？
邬屈奥义： 广度

马龙县13776817538： 急!!C++深度优先算法和广度优先算法 - ？
邬屈奥义： 以搜索为例,下面两种介绍了深搜与广搜的具体实现. 算法博大精深,望楼主好好学习啊 1. 深度搜索 void Graph::DFS(const int v, int visited[]) { cout<visited[v] = 1; //顶点 v 作访问标记 int w = GetFirstNeighbor(v););//取 v 的第一个邻...

马龙县13776817538： 图遍历的算法 - ？
邬屈奥义： 图的遍历方法目前有深度优先搜索法和广度(宽度)优先搜索法两种算法. 深度优先搜索法是树的先根遍历的推广,它的基本思想是:从图G的某个顶点v0出发,访问v0,然后选择一个与v0相邻且没被访问过的顶点vi访问,再从vi出发选择一个...

马龙县13776817538： 深度优先搜索遍历和广度优先搜索的遍历序列及具体步骤和原因, - ？
邬屈奥义： 1->2->3->4 (表示1可达到2,达到3,达到4) 2->1->3->5 3->1->2->4->5->6 4->1->3->6 5->2->3->6 6->3->4->5 广度优先搜索就是把每一行按照顺序输出,去掉重复的,即先看1,有1,2,3,4,然后看2,因为有3,4了,所以只要5,然后看3,以此...

马龙县13776817538： 数据结构 深度优先遍历和广度 - ？
邬屈奥义： 无向图:两个结点之间的路径没有方向区分 有向图:两个结点之间的路径有方向区分,从A到B的路径长和从B到A的路径长可以不同 深度优先遍历:从给定结点出发,选取它的邻接结点中某个未被访问的结点访问.被访问的结点成为新的给定结点.重复上述过程,直到当前结点没有未被访问的邻接结点.接着开始回溯,返回上一次访问的结点继续寻找其未被访问的邻接结点,直至完成遍历. 广度优先遍历:从给定结点出发,依次访问它的所有邻接结点.然后按照这些结点的被访问顺序,依次访问这些结点的所有邻接结点.重复上述过程,直至完成遍历.

马龙县13776817538： 请大牛通俗的解释下深度优先和广度优先,最好举个例子哈...... - ？
邬屈奥义： 好.我来给你“通俗”的解释一下.比如说你在校园里看到一个非常pretty的背影,长发,白裙.可惜她立刻就不见了.你要在学校里寻找这位mm.假设现...