NowCode Intorduction---DFS&BFS

搜索

? 通过不停的试探去寻找解的一种算法。
? 与其说是一种算法，不如说是一种方法。
? 基础的方法有暴力的搜索法，深搜，广搜三种。
? 更高级的有IDDFS，DBFS，A，IDA等等

深度优先搜索（dfs）

“一条道走到黑”“走不了了再倒回去”
算法过程：

VOID DFS(状态 A)
1. 判断当前的状态是否合法。合法则继续执行，否则则回到上次调用。
2. 先下走一层，也就是调用DFS(状态 A + Δ)

主要过程——DFS 大体框架

? 试探节点A ? A是否满足在这个图（或树）中
? 如果在，标记A如果已经被试探过的话，所影响的各种值；
? 紧接着，去试探所有的A可以达到的节点；
? 等待所有的都执行完之后，还原标记A

广度优先搜索（Bfs）

? 一层一层的走！
? 广搜总是每次都把离上一状态最近的状态用一个队列记录下来；
? 记录之后，检查队列是否为空，如果不为空，就讲队首元素弹出，并且以这个状态为“根节点”进行广度优先搜索。
? 直到整个队列为空为止。

对于坐标的处理方法

? 本来是用两个数来表示的坐标(x, y)，可以用一个数来表示。
? 为什么要这样？简便呗！
? 第i行第j列的格子编号为i*m+j
? （横纵坐标的起点都是0）
? 反之，编号为u的节点，其行号和列号分别为u / m; u % m

优化搜索的思路：

? 核心：减小搜索树的大小
? 方法：
? 一、改变搜索顺序
? 二、剪枝 ：最优化剪枝 & 可行性剪枝

NowCode Intorduction---DFS&BFS

原文：https://www.cnblogs.com/bingers/p/13197736.html