Algorithm-Pattern
  • Introduction
  • C & C++
    • C语言
      • C/C++编译器
      • 宏的使用
      • 编译过程
      • 指针 & 数组
      • 柔性数组
      • 函数指针 & 回调函数
      • C标准库之stdio
      • C标准库之string
      • C标准库之errno
      • C标准库之stdarg
      • C标准库之regex
    • C++基础语法
      • 自增(++) & 自减(--)
      • c语言到c++
      • 可变模板参数
      • 强制类型转换
      • C/C++类型转换的本质
      • 指针 & 引用
      • const的用法
      • static的用法
      • 重要的关键字(一)
      • 重要的关键字(二)
      • 内存申请和释放
      • 内联函数
      • 函数 & 运算符重载
      • 面向对象之封装
      • 构造函数 & 析构函数
      • 面向对象之继承
      • 面向对象之多态
      • 泛型编程
      • 异常
      • 再谈函数指针
    • C++并发编程
      • C++的锁
      • 并发与多线程
    • C++高级特性
      • 函数对象
      • 移动语义 & 完美转发
      • lambda表达式
      • RTTI技术
      • RAII技术
      • 智能指针
      • 模板的特化
      • C++静态库和动态库
      • 内存溢出和内存泄漏
    • STL基础
      • String
      • array/vector/list
      • deque/priority_queue
      • set/map
      • unordered_set/unordered_map
      • algorithm_1
      • functional
      • allocator
    • C++标准库
      • IO
      • Tuple
      • regex
      • bitset
      • numeric
    • STL深入源码
      • vector内部实现
      • deque内部实现
      • sort函数实现
    • 第三方库
      • JsonCpp
      • ProtoBuf
  • 数据结构
    • 线性表
    • 字符串
    • 栈和队列
    • 二叉树
    • 平衡二叉树
    • 平衡多路搜索树
    • 树结构的延申
    • 图
    • 二进制
    • 散列表
  • 算法基础
    • 排序算法
    • 查找算法
    • 数学问题
    • 并查集
    • 递归算法
    • 附加——主定理
    • Catalan数
  • 算法设计思想
    • 滑动窗口思想
    • BFS/DFS
    • 二分法
    • 回溯法
    • 贪心算法
    • 分治法
    • 动态规划
    • 分支限界算法
    • 有限状态机(FSM)
  • LeetCode系列
    • 死磕二叉树
    • 股票买卖问题
    • 打家劫舍问题
    • 跳跃游戏问题
    • 括号匹配问题
    • 石子游戏问题
    • 子序列问题
    • 数组 & 矩阵
    • 排列 & 组合
  • 经典算法问题
    • 几何问题
    • 区间问题
    • 背包问题
    • 石子堆问题
    • 表达式求值
  • 面试题
    • 数据结构和算法基础
    • 程序设计题
      • 实现双线程交替打印
      • C++实现读写锁
      • 实现阻塞队列
      • 实现环形队列
      • 实现线程池
      • 实现智能指针
      • 实现string类
      • 实现高性能local cache
      • 实现内存池
      • 生产者-消费者模型
      • 设计定时器
    • 经典的算法题
    • C++面试题总结
    • 面试算法题总结
由 GitBook 提供支持
在本页
  • 1、DFS
  • 题型
  • 2、BFS
  • 算法框架
  • 题型

这有帮助吗?

  1. 算法设计思想

BFS/DFS

上一页滑动窗口思想下一页二分法

最后更新于4年前

这有帮助吗?

1、DFS

DFS算法就是回溯算法的思想,迭代的实现中往往需要「栈」这种数据结构用来回退,递归的实现中往往是在递归出口的位置得到全局的解。

题型

2、BFS

BFS 的核心思想就是把一些问题解空间抽象在一个图中,从一个点开始,向四周开始扩散。一般来说,我们用迭代写 BFS 算法都是用「队列」这种数据结构,每次将一个节点周围的所有节点加入队列。如果是递归实现,则递归返回的是子问题的解。

BFS 相对 DFS 的最主要的区别是:BFS 找到的路径一定是最短的,但代价就是空间复杂度比 DFS 大很多。

算法框架

问题的本质就是让你在一幅「图」中找到从起点 start 到终点 target 的最近距离,这个例子听起来很枯燥,但是 BFS 算法问题其实都是在干这个事。

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路,有一种trick就是 暂时替换,防止重复进入

    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点:这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点:更新步数在这里 */
        step++;
    }
}

队列 q 就不说了,BFS 的核心数据结构;cur.adj() 泛指 cur 相邻的节点,比如说二维数组中,cur 上下左右四面的位置就是相邻节点;visited 的主要作用是防止走回头路,大部分时候都是必须的,但是像一般的二叉树结构,没有子节点到父节点的指针,不会走回头路就不需要 visited。

1、为什么 BFS 可以找到最短距离,DFS 不行吗?

首先, BFS 的逻辑是,depth 每增加一次,队列中的所有节点都向前迈一步,这保证了第一次到达终点的时候,走的步数是最少的。

DFS 不能找最短路径吗?其实也是可以的,但是时间复杂度相对高很多。因为 DFS 实际上是靠递归的堆栈记录走过的路径,你要找到最短路径,肯定得把二叉树中所有树杈都探索完才能对比出最短的路径有多长对不对?而 BFS 借助队列做到一次一步「齐头并进」,是可以在不遍历完整棵树的条件下找到最短距离的。

形象点说,DFS 是线,BFS 是面;DFS 是单打独斗,BFS 是集体行动。

2、既然 BFS 那么好,为啥 DFS 还要存在?

BFS 可以找到最短距离,但是空间复杂度高,而 DFS 的空间复杂度较低。

拿二叉树的最小高度问题的例子,假设给你的这个二叉树是满二叉树,节点数为 N,对于 DFS 算法来说,空间复杂度无非就是递归堆栈,最坏情况下顶多就是树的高度,也就是 O(logN)。

但是 BFS 算法,队列中每次都会储存着二叉树一层的节点,这样的话最坏情况下空间复杂度应该是树的最底层节点的数量,也就是 N/2,用 Big O 表示的话也就是 O(N)。

由此观之,BFS 还是有代价的,一般来说在找最短路径的时候使用 BFS,其他时候还是 DFS 使用得多一些(主要是递归代码好写)。

题型

✏️
✏️
Open the Lock