个人网站学生作业,创客贴平面设计在线官网,最近播放中文版在线观看电视剧,进入百度知道首页深度优先搜索和广度优先搜索关于搜索遍历对于搜索来说#xff0c;我们绝大多数情况下处理的都是叫 “所谓的暴力搜索” #xff0c;或者是说比较简单朴素的搜索#xff0c;也就是说你在搜索的时候没有任何所谓的智能的情况在里面考虑#xff0c;很多情况下它做的一件事… 深度优先搜索和广度优先搜索关于搜索遍历对于搜索来说我们绝大多数情况下处理的都是叫 “所谓的暴力搜索” 或者是说比较简单朴素的搜索也就是说你在搜索的时候没有任何所谓的智能的情况在里面考虑很多情况下它做的一件事情就是把所有的结点全部遍历一次然后找到你要的结果。基于这样的一个数据结构如果这个数据结构本身是没有任何特点的也就是说是一个很普通的树或者很普通的图。那么我们要做的一件事情就是遍历所有的结点。同时保证每个点访问一次且仅访问一次最后找到结果。那么我们先把搜索整个先化简情况我们就收缩到在树的这种情况下来进行搜索。如果我们要找到我们需要的一个值在这个树里面我们要怎么做那么毫无疑问就是从根这边开始先搜左子树然后再往下一个一个一个一个点走过去然后走完来之后再走右子树直到找到我们的点这就是我们所采用的方式。再回到我们数据结构定义它只有左子树和右子树。我们要实现这样一个遍历或者搜索的话毫无疑问我们要保证的事情就是每个结点都要访问一次每个结点仅仅要访问一次对于结点访问的顺序不限深度优先Depth First Search广度优先Breadth First Search仅访问一次的意思就是代表我们在搜索中我们不想做过多无用的访问不然的话我们的访问的效率会非常的慢。当然的话还可以有其余的搜索其余的搜索的话就不再是深度优先或者广度优先了而是按照优先级优先 。当然你也可以随意定义比如说从中间优先类似于其他的东西但只不过的话你定义的话要有现实中的场景。所以你可以认为是一般来说就是深度优先、广度优先另外的话就是优先级优先。按照优先级优先搜索的话其实更加适用于现实中的很多业务场景而这样的算法我们一般把它称为启发式搜索更多应用在深度学习领域。而这种比如说优先级优先的话在很多时候现在已经应用在各种推荐算法和高级的搜索算法让你搜出你中间最感兴趣的内容以及每天打开抖音、快手的话就给你推荐你最感兴趣的内容其实就是这个原因。深度优先搜索(DFS)递归写法递归的写法一开始就是递归的终止条件然后处理当前的层然后再下转。那么处理当前层的话就是相当于访问了结点 node然后把这个结点 node 加到已访问的结点里面去那么终止条件的话就是如果这个结点之前已经访问过了那就不管了那么下转的话就是走到它的子结点二叉树来说的话就是左孩子和右孩子如果是图的话就是连同的相邻结点如果是多叉树的话这里就是一个children,然后把所有的children的话遍历一次。二叉树模版def dfs(node): if node in visited: # already visited return visited.add(node) # process current node # ... # logic here dfs(node.left) dfs(node.right)多叉树模版visited set()def dfs(node, visited): if node in visited: # terminator # already visited return visited.add(node) # process current node here. ... for next_node in node.children(): if next_node not in visited: dfs(next_node, visited)非递归写法def DFS(self, tree): if tree.root is None: return [] visited, stack [], [tree.root] while stack: node stack.pop() visited.add(node) process (node) nodes generate_related_nodes(node) stack.push(nodes) # other processing work ...遍历顺序我们看深度优先搜索或者深度优先遍历的话它的整个遍历顺序毫无疑问根节点 1 永远最先开始的接下来往那个分支走其实都一样的我们简单起见就是从最左边开始走那么它深度优先的话就会走到底。参考多叉树模版我们可以在脑子里面或者画一个图把它递归起来的话把递归的状态树画出来就是这么一个结构。就比如说它开始刚进来的话传的是 root 的话root 就会先放到 visited 里面表示 root 已经被 visit,被 visited之后就从 root.childern里面找 next_node所有它的next_node都没有被访问过的所以它就会先访问最左边的这个结点这里注意当它最左边这个结点先拿出来了判断没有在 visited里面因为除了 root之外其他结点都没有被 visited过那么没有的话它就直接调dfsnext_node 就是把最左边结点放进去再把 visited也一起放进去。递归调用的一个特殊它不会等这个循环跑完它就直接会进到下一层了也就是当前梦境的话这里写了一层循环但是在第一层循环的时候我就要开始下钻到新的一层梦境里面去了。所以在这里的话图的遍历顺序广度优先搜索(BFS)广度优先遍历它就不再是用递归也不再是用栈了而是用所谓的队列。你可以把它想象成一个水滴滴到1这个位置然后它的水波纹一层一层一层扩散出去就行了。两者对比BFS代码模版# Pythondef BFS(graph, start, end): visited set() queue [] queue.append([start]) while queue: node queue.pop() visited.add(node) process(node) nodes generate_related_nodes(node) queue.push(nodes) # other processing work ...部分图片来源于网络版权归原作者侵删。?点击阅读原文查看往期内容 快留言?和我互动吧