DFS.md

深度优先遍历

介绍

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。

因发明「深度优先搜索算法」，约翰 · 霍普克洛夫特与罗伯特 · 塔扬在 1986 年共同获得计算机领域的最高奖：图灵奖。

截止目前（2020-02-21），深度优先遍历在 LeetCode 中的题目是 129 道。在 LeetCode 中的题型绝对是超级大户了。而对于树的题目，我们基本上都可以使用 DFS 来解决，甚至我们可以基于 DFS 来做广度优先遍历。并不一定说 DFS 不可以做 BFS（广度优先遍历）的事情。而且由于 DFS 通常我们可以基于递归去做，因此算法会更简洁。 在对性能有很高邀请的场合，我建议你使用迭代，否则尽量使用递归，不仅写起来简单快速，还不容易出错。

另外深度优先遍历可以结合回溯专题来联系，建议将这两个专题放到一起来学习。

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

算法流程

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

这里的 stack 可以理解为自实现的栈，也可以理解为调用栈

算法模板

const visited = {}
function dfs(i) {
	if (满足特定条件）{
		// 返回结果 or 退出搜索空间
	}

	visited[i] = true // 将当前状态标为已搜索
	for (根据i能到达的下个状态j) {
		if (!visited[j]) { // 如果状态j没有被搜索过
			dfs(j)
		}
	}
}

题目推荐

这是我近期总结的几个 DFS 题目，后续会持续更新～

• 200. 岛屿数量 中等

• 695. 岛屿的最大面积 中等

• 979. 在二叉树中分配硬币 中等