深度优先搜索

dfs与bfs的区别

• dfs是可一个方向去搜，直到搜不下去了，再换方向（换方向的过程涉及到回溯）
• bfs是先把本节点所连接的所有节点遍历一遍，走到下一个节点的时候，再把连接节点的所有节点遍历一遍，搜索方向更像是广度，四面八方的搜索过程

dfs的模板

深度优先搜索与回溯模板类似，深搜三部曲：

1. 确定递归函数的参数与返回值：返回值一般是void
2. 确定递归的终止条件
3. 确定单层递归的逻辑

void backtracking( 参数 ){
		// 终止条件
		if( 终止条件 ){
				收集结果（通常在叶子节点收集结果）
				return;
		}
		// 单层逻辑（通常为一个for循环，每次循环都继续递归）
		for(集合元素集){
				// 处理节点的操作
				// 递归
				// 回溯（还原，撤销对节点的操作）
		}
}

广度优先搜索

广搜的使用场景

<aside> 💡 广搜的搜索方式适合于解决两个点之间的最短路径问题

</aside>

也有一些问题是广搜 和 深搜都可以解决的，例如岛屿问题，这类问题的特征就是不涉及具体的遍历方式，只要能把相邻且相同属性的节点标记上就行。

广搜的过程

广搜（bfs）是一圈一圈的搜索过程

bfs代码

使用一个容器保存遍历过的元素，可以使用队列、栈，甚至是数组

一般使用队列