📄️ 5.1 算法解释
深度优先搜索和广度优先搜索是两种最常见的优先搜索方法,它们被广泛地运用在图和树等结构中进行搜索。
📄️ 5.2 深度优先搜索
深度优先搜索(depth-first search,DFS)在搜索到一个新的节点时,立即对该新节点进行遍历;因此遍历需要用先入后出的栈(stack)来实现,也可以通过与栈等价的递归来实现。对于树结构而言,由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进。在 Python 中,我们可以用 collections.deque 来实现 C++ 中的 stack。但是通常情况下,我们还是会选用 C++ 中的 vector 或 Python 中的 list 来实现栈,因为它们既是先入后出的数据结构,又能支持随机查找。
📄️ 5.3 回溯法
回溯法(backtracking)是优先搜索的一种特殊情况,又称为试探法,常用于需要记录节点状态的深度优先搜索。通常来说,排列、组合、选择类问题使用回溯法比较方便。
📄️ 5.4 广度优先搜索
广度优先搜索(breadth-first search,BFS)不同与深度优先搜索,它是一层层进行遍历的,因此需要用先入先出的队列 (queue) 而非先入后出的栈 (stack) 进行遍历。由于是按层次进行遍历,广度优先搜索时按照“广”的方向进行遍历的,也常常用来处理最短路径等问题。在 Python 中,我们可以用 collections.deque 来实现 C++ 中的 queue。
📄️ 5.5 练习
基础难度