深度优先搜索,简称DFS
初始节点出发,按预定的顺序扩展到下一个节点,然后从下一节点出发继续扩展新的节点,不断递归执行这个过程,直到某个节点不能再扩展下一个节点为止。此时,则返回上一个节点重新寻找一个新的扩展节点。如此搜索下去,直到找到目标节点,或者搜索完所有节点为止。
原文链接-传送门
广度优先搜索,简称BFS
它是一种图搜索算法,它通过逐层遍历图的节点来查找目标
或许有些人会认为它跟深搜差别不大,但我想说你错了,深搜和广搜有着一些共同点但更多的是不同点,下面我就分开讲讲:
深度优先搜索(DFS):
> 简单来说就是走迷宫,给定一个入口和一个出口,问你能不能走出去,如果能输出"YES",不能输出"NO"
> 你可以选择往前走,直到遇到死胡同,然后再回头,选择另外一个方向继续前进,直到找到出口。这个过程,就是深度优先搜索的一个形象展现。
但广搜就会简单很多:
广度优先搜索(BFS):
> 它的特点是一层一层地进行搜索,每一层的节点都会被访问到,然后再进入下一层。这种方式就好比我们在寻找某个城市的地铁站,先从起点站开始,然后逐站寻找,直到找到目标站为止。
你可以理解为我要找我的朋友,我就可以先从XX区找起,在找到了之后再在XX区内找小区,接着再往下执行该操作,最终找到朋友,这就是广搜的一种体现
> 深度优先搜索,如同其名,它的特点是尽可能深地搜索树的分支。这种策略在搜索大树时非常有效,因为它可以快速找到解决方案,或者在没有解决方案的情况下,快速排除某些路径。然而,这种策略也有其局限性,例如,它可能会在搜索过程中陷入无限循环。为了避免这种情况,我们通常需要在实现深度优先搜索时,加入一些特殊的检查机制。
> 广度优先搜索则是一种层次遍历的策略,它会先搜索离根节点最近的节点,然后再搜索下一层的节点。这种策略在搜索最短路径问题时非常有效,因为它总是先搜索离根节点最近的路径,所以一旦找到解决方案,那么这个解决方案就是最短的。然而,广度优先搜索需要存储所有的节点,因此在空间复杂度上,通常会比深度优先搜索要大。
> 让我们通过一个实际的例子来理解这两种搜索策略。假设我们想要找到从A地点到B地点的路线。如果我们使用深度优先搜索,那么我们可能会先找到一条从A到B的路线,但这条路线可能不是最短的。如果我们使用广度优先搜索,我们会先找到所有从A出发可以到达的地点,然后再从这些地点出发,找到可以到达B的地点。这样,我们找到的第一条路线,就是最短的路线。
> 在实际的应用中,我们应该根据问题的特性,选择最适合的搜索策略。例如,如果我们需要找到所有可能的解决方案,那么深度优先搜索可能会更有效。而如果我们需要找到最短的解决方案,那么广度优先搜索可能会更合适。
> 原文链接-传送门
接下来聊聊代码:
深度优先搜索:
---以下内容来自:小码王学习软件HTTPS://ONLINE.XIAOMAWANG.COM/:深度优先搜索(二)作业第一题
代码:
紧接着是 广度优先搜索
---以下内容来自:小码王学习软件HTTPS://ONLINE.XIAOMAWANG.COM/:广度优先搜索(一)第二模块广度优先搜索第二题
代码:
最后说说心得,八个字:
再也不想见到它了
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
注:抄的我都标记了,不信自己查