<small id='zGvwxY8'></small> <noframes id='7mFPTZt'>

  • <tfoot id='djbG'></tfoot>

      <legend id='9IasnwHP4'><style id='rdfcQ'><dir id='1Gx2v7bh'><q id='gbYol'></q></dir></style></legend>
      <i id='XoxelJ'><tr id='0EXpwv'><dt id='Wubm'><q id='Hm7ar9OI48'><span id='O56Lwf'><b id='7qGjTw'><form id='kV1vhScL'><ins id='e6NS'></ins><ul id='b8ORH'></ul><sub id='iwsN4G1'></sub></form><legend id='qTRO'></legend><bdo id='wYxCF'><pre id='W3tFAi9h'><center id='glT7iJeLR'></center></pre></bdo></b><th id='RFZcBHvg6t'></th></span></q></dt></tr></i><div id='MtYVbPRL1'><tfoot id='yvE24inIkC'></tfoot><dl id='9tiU'><fieldset id='r7oDAT2JR'></fieldset></dl></div>

          <bdo id='paFTnZ6U'></bdo><ul id='adoDshbLx'></ul>

          1. <li id='fytlhJaI'></li>
            登陆

            章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFS

            admin 2019-09-07 140人围观 ,发现0个评论

            Python学习教程:行列和 BFS —— 栈和 DFS

            行列和 BFS:

            广度优先查找(BFS)的一个常见应用是找出从根结点到方针结点的最短途径。

            示例

            这儿咱们供给一个示例来阐明怎么运用 BFS 来找出根结点 A 章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFS和方针结点 G 之间的最短途径。

            观察

            观章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFS看上面的动画后,让咱们答复以下问题:

            1. 结点的处理次序是什么?

            在第一轮中,章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFS咱们处理根结点。在第二轮中,咱们处理根结点周围的结点;在第三轮中,咱们处理距根结点两步的结点;等等等等。

            与树的层序遍历相似,越是挨近根结点的结点将越早地遍历。

            如果在第 k 轮中将结点 X 增加到行列中,则根结点与 X 之间的最短途径的长度恰好是 k。也便是说,第一次找到方针结点时,你现已处于最短途径中。

            2. 行列的入队和出队次序是什么?

            如上面的动画所示,咱们首要将根结点排入行列。然后在每一轮中,咱们逐一处理现已在行列中的结点,并将一切街坊增加到行列中。值得注意的是,新增加的节点不会当即遍历,而是鄙人一轮中处理。

            结点的处理次序与它们增加到行列的次序是彻底相同的次序,即先进先出(FIFO)。这便是咱们在 BFS 中运用行列的原因。

            栈和 DFS:

            与 BFS 相似,深度优先查找(DFS)也可用于查找从根结点到方针结点的途径。在本文中,咱们供给了示例来解说 DFS 是怎么作业的以及栈是怎么逐渐协助 DFS 作业的。

            示例

            咱们来看一个比如吧。咱们期望经过 DFS 找出从根结点 A 到方针结点 G 的途径。

            观察

            观看上面的动画后,让咱们答复以下问题:

            1. 结点的处理次序是什么?

            在上面的比如中,咱们从根结点 A 开端。首要,咱们挑选结点 B 的途径,并进行回溯,直到咱们抵达结点 E,咱们无法更进一步深化。然后咱们回溯到 A 并挑选第二条途径到结点 C 。从 C 开端,咱们测验第一条途径到 E 可是 E 已被访问过。所以咱们回到 C 并测验从另一条途径到 F。最终,咱们找到了 G。

            总的来说,在咱们抵达最深的结点之后,咱们只会回溯并测验另一条途径。

            因而,你在 DFS 中找到的第一条途径并不总是最短的途径。例如,在上面的比如中,咱们成功找出了途径章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFS A-> C-> F-> G 并中止了 DFS。但这不是从 A 到 G 的最短途径。

            2. 栈的入栈和退栈次序是什么?

            如上面的动画所示,咱们首要将根结点推入到栈中;然后咱们测验第一个街坊 B 并将结点 B 推入到栈中;等等等等。当咱们抵达最深的结点 E 时,咱们需求回溯。当咱们回溯时,史上最强师兄咱们将从栈中弹出最深的结点,这实际上是推入到栈中的最终一个结点。

            结点的处理次序是彻底相反的次序,就像它们被增加到栈中一样,它是后进先出(LIFO)。这便是咱们在 DFS 中运用栈的原因。

            总结:

            明显BFS能够找到根节点到方针节点最短的途径,DFS能够最快的找到根节点到方针节点的道路,但却纷歧定是最短的。详细可参阅维基百科:

            BFS:https://zh.wikipedia.org/wiki/广度优先查找

            DFS:https://zh.wikipe章鱼彩票 苹果-Python学习教程:队列和 BFS——栈和 DFSdia.org/wiki/深度优先查找

            请关注微信公众号
            微信二维码
            不容错过
            Powered By Z-BlogPHP