深度优先搜索(DFS)与宽度优先搜索(BFS) |
您所在的位置:网站首页 › 代价树的广度优先搜索和广度优先搜索 › 深度优先搜索(DFS)与宽度优先搜索(BFS) |
深度优先搜索和宽度优先搜索是两种不用的搜索理念。 深度优先搜索 深度优先搜索会选择当前节点的一个子节点进行深入,然后对子节点再进行深度优先搜索,一直搜索到叶节点,然后向上回溯,再对另一个子节点进行深度优先搜索。既先进行深度搜索,深度搜索无目标时进行宽度搜索。找到目标则结束搜索。 深度优先搜索用栈(stack)来实现 1、把根节点压入栈中。 2、从栈中弹出一个元素,检查是否为目标元素,如果是则结束。如果不是,则将其所有的子节点压入栈中,然后重复此步骤。 3、如果树遍历完毕还没有搜素到则结束。 宽度优先搜索(又称广度优先搜索)宽度优先搜索则是对于当前节点,首先将当前节点的所有子节点都搜索一遍,如果没有目标,则对每一个子节点进行广度搜索,直到找到目标或者搜索完毕。既先进行宽度搜索,宽度搜索无目标时进行深度搜索。找到目标则结束搜索。 宽度优先搜索使用队列(queue)来实现,整个过程也可以看做一个倒立的树形: 1、把根节点放到队列的末尾。 2、从队列的头部取出一个元素,检查是否为目标元素,如果是则结束。如果不是则将这个节点的所有子节点放到队列的末尾。然后重复此步骤。 3、如果树遍历完毕还没有搜素到则结束。 示例对于以上树: 深度优先搜索的搜索顺序为:A->B->D->H->E->C->F->G 广度优先搜索的搜索顺序为:A->B-->C->D->E->F->G->H 参考: 百度百科:深度优先搜索 百度百科:宽度优先搜索 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |