搜索一般指在有限的状态空间中进行枚举，通过穷尽所有的可能来找到符合条件的解或者解的个数。 根据搜索方式的不同，搜索算法可以分为 DFS，BFS，双向搜索，A*算法等。这里只介绍 DFS/BFS，以及发生在 DFS 上一种技巧-回溯。

DFS

DFS 的概念来自于图论，但是搜索中 DFS 和图论中 DFS 还是有一些区别，搜索中 DFS 一般指的是通过递归函数实现暴力枚举。

算法流程

1. 首先将根节点放入stack中。
2. 从stack中取出第一个节点，并检验它是否为目标。如果找到目标，则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入stack中。
3. 重复步骤 2。
4. 如果不存在未检测过的直接子节点。将上一级节点加入stack中。 重复步骤 2。
5. 重复步骤 4。
6. 若stack为空，表示整张图都检查过了——亦即图中没有欲搜寻的目标。结束搜寻并回传“找不到目标”。 PS: 这里的 stack 可以理解为自实现的栈，也可以理解为调用栈

算法模板

function dfs(i) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
	}
 
	visited[i] = true // 将当前状态标为已搜索
	for (根据i能到达的下个状态j) {
		if (!visited[j]) { // 如果状态j没有被搜索过
			dfs(j)
		}
	}
}

BFS

BFS 也是图论中算法的一种，不同于 DFS 的是 BFS 采用横向搜索的方式，在数据结构上采用队列结构。

算法流程

1. 首先将根节点放入队列中。
2. 从队列中取出第一个节点，并检验它是否为目标。
   • 如果找到目标，则结束搜索并回传结果。
   • 否则将它所有尚未检验过的直接子节点加入队列中。
3. 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。
4. 重复步骤 2。

算法模板

function bfs() {
	let q = new Queue()
	q.push(初始状态)
	while(q.length) {
		let i = q.front()
		for (i的可抵达状态j) {
			if (j 合法) {
				q.push(j)
			}
		}
	}
	// 找到所有合法解
}

回溯

回溯是 DFS 中的一种技巧。回溯法采用 试错 的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。 本质上讲，回溯是一种走不通就回头的算法。

算法流程

1. 构造空间树。
2. 进行遍历。
3. 如遇到边界条件，即不再向下搜索，转而搜索另一条链。
4. 达到目标条件，输出结果。

算法模板

回溯是 DFS 上的一种技巧

function dfs(i) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
	}
 
	visited[i] = true // 将当前状态标为已搜索
	dosomething(i) // 对i做一些操作
	for (根据i能到达的下个状态j) {
		if (!visited[j]) { // 如果状态j没有被搜索过
			dfs(j)
		}
	}
	undo(i) // 恢复i
}