DFS And BFS

Thinking Patterns - DFS v.s. Backtrack

Problems - Islands Problems

Problems Possible Solutions Key Points Code Similar Problems Comments
200. Number of Islands dfs, bfs code
1254. Number of Closed Islands dfs, bfs code
1905. Count Sub Islands dfs, bfs, union-find code 1992
1020. Number of Enclaves dfs, bfs code
694. Number of Distinct Islands dfs, bfs code
695. Max Area of Island dfs, bfs code
-

Key Points

  1. 694 How to present the shape of islands with BFS and DFS?

Complexity Analyze

  1. 200.

Time Complexity

  1. O(N+4N) = O(N) N = m*n
  2. Loop all the node outside, m*n
  3. Overall O(N)

Space Complexity

  1. For DFS, Recursive stack depth: worst at O(N)
  2. For BFS, Queue length: worst at O(N)
  3. Worst case example, m=1, n = N, and all equals 1
  4. Use grid as visited, no extra spaces
  1. 1254, 1905, 1020, 694

Similar as 200

Problems - N-nary Tree

Problems Possible Solutions Key Points Code Similar Problems Comments
931. Minimum Falling Path Sum DP
dfs		 dp
dfs
-

BFS

Thinking Patterns

  1. BFS算法的本质就是二叉树的层序遍历。

  2. 衍生到多叉树的层序遍历，和图的遍历（增加visited数组）

  3. BFS 算法经常用来求解最短路径问题。最短路径，都可以类比成二叉树最小深度问题（寻找距离根节点最近的叶子节点），递归遍历必须要遍历整棵树的所有节点才能找到目标节点，而层序遍历不需要遍历所有节点就能搞定，所以层序遍历适合解决最短路径问题。

BFS Problems

Problems Possible Solutions Key Points Code Similar Problems Comments
773. Sliding Puzzle bfs code
752. Open the Lock bfs code
919. Complete Binary Tree Inserter bfs code
841. Keys and Rooms bfs code
433. Minimum Genetic Mutation bfs code
1926. Nearest Exit from Entrance in Maze bfs code
1091. Shortest Path in Binary Matrix bfs code
994. Rotting Oranges bfs code
721. Accounts Merge bfs, dfs, union-find bfs
union-find
127. Word Ladder bfs bfs
365. Water and Jug Problem bfs bfs
-

Complexity Analyze

Refer to the code

results matching ""

    No results matching ""