DFS 与 BFS 的区别

基于遍历行为的区别

  • DFS 是以(递归)为基础实现的

一往直前,不见黄河心不死,当无法向下递归后,将当前的栈顶任务处理完后,弹栈接着处理任务,直到栈为空,

那DFS是如何避免任务被重复执行?

我的理解是: 基于的机制,实际上DFS会将从入口处到终点处的所有任务,全部遍历出来,并逐一从尾到头一一执行任务,因此并不会出现重复执行任务的情况

DFS的执行方式类似于,二叉树的前序,中序,后序遍历

  • BFS 是以队列为基础实现的

BFS是逐层遍历,类似于二叉树中的层次遍历

BFS首先将起点压入队列当中,然后,每次弹出队首元素,并将队首元素中的所有有效的状态逐一压入队列中
需要注意的是,状态是否有效,需要自行判断,即可能会出现重复遍历之前遍历的节点的情况,因此,在使用BFS时,需要自己去判断是否是有效的状态(这里的状态是抽象概念,比如对于迷宫,在迷宫的每个位置,状态有四种,状态即方向)

基于内存的区别

  • DFS的内存取决于递归的深度即`栈的空间

状态数对于递归的深度没有太多的影响,类比于树的遍历,节点的出度数就是状态数,而递归的深度,取决于数的深度

  • BFS的内存取决于状态数,因为BFS需要将所有的有效状态装入队列中,因此BFS相比DFS会占用更多的空间

本文标题:DFS 与 BFS 的区别

文章作者:定。

发布时间:2017年8月25日 - 22时08分

本文字数:579字

原始链接:http://cocofe.cn/2017/08/25/DFS 与 BFS 的区别/

许可协议: Attribution-NonCommercial 4.0

转载请保留以上信息。