【LeetCode】BFS

手动 redirect：【Day 3】系统模型、容错、高可用

因为写了 DFS，感觉不得不来一下 BFS。

BFS：先把这一层能走访的元素先走了，再到下一层去。所以用 FIFO 的 queue 或等价的递回做。

不只是用在 树 或 图！

虽然提到 DFS 或 BFS 这两种寻访 / 爆破（brute force）方法，
通常会想到 tree traversal 或是 graph traversal，
但在某些输入为 array 的题目，也能用到这样的概念呢！
45. Jump Game II
1306. Jump Game III

蛮值得培养一下这样的思考，
至少以我来说，跳跳游戏系列都还蛮戳中我思考死穴的。

要用 BFS 还是 DFS？

it depends.
虽然很干话，
但对於树或图的题目，通常能用 BFS 就可以用 DFS，
时间复杂度大致相同（还是有不同的时候），但根据输入的测资可能实际时间上会有差异。
所以应该要能够在当下思考、提出这两者之间的差异，
并依据需求去选择。

真的要总结的话，
DFS 重点在於递回和 backtrack，在图中比较常使用 DFS。
BFS 重点在於把当下所有可能都记录下来，适合大范围地寻找、最短路径，耗费较多额外空间。