Update 01.Graph-DFS.md

itcharge · itcharge · commit 374531fdb881 · 2022-09-05T16:11:32.000+08:00
diff --git a/Contents/08.Graph/02.Graph-Traversal/01.Graph-DFS.md b/Contents/08.Graph/02.Graph-Traversal/01.Graph-DFS.md
@@ -2,17 +2,17 @@
 
 ## 1. 深度优先搜索简介
 
-> **深度优先搜索算法**（Depth First Search）：英文缩写为 DFS。是一种用于遍历或搜索树或图的算法。该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 `v` 的所在边都己被探寻过，搜索将回溯到发现节点 `v` 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
+> **深度优先搜索算法**（Depth First Search）：英文缩写为 DFS。是一种用于搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。
 
-深度优先搜索使用的是回溯思想，这种思想很适合使用「递归」来实现。而递归对问题的处理顺序，遵循了「后进先出」的规律。所以递归问题的处理，需要借助「堆栈」来实现。
+深度优先搜索采用了回溯思想，该算法沿着树的深度遍历树的节点，会尽可能深的搜索树的分支。当节点 `v` 的所在边都己被探寻过，搜索将回溯到发现节点 `v` 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
 
-在深度优先遍历的过程中，我们需要将当前遍历节点 `v` 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，所以深度优先搜索可以通过「递归」或者「堆栈」来实现。
+在深度优先遍历的过程中，我们需要将当前遍历节点 `v` 的相邻节点暂时存储起来，以便于在回退的时候可以继续访问它们。遍历到的节点顺序符合「后进先出」的特点，这正是「递归」和「堆栈」所遵循的规律，所以深度优先搜索可以通过「递归」或者「堆栈」来实现。
 
 ## 2. 深度优先搜索过程演示
 
 接下来我们以一个无向图为例，演示一下深度优先搜索的过程。
 
-我们用邻接字典的方式存储无向图结构，对应结构代码如下：
+我们用邻接字典的方式存储无向图结构，对应结构如下：
 
 ```Python
 # 定义无向图结构
@@ -26,23 +26,25 @@ graph = {
 }
 ```
 
-该无向图的结构如图左所示，图右为深度优先搜索的遍历路径。
+该无向图对应的邻接字典表示：无向图中有 `A`、`B`、`C`、`D`、`E`、`F` 共 `6` 个节点，其中与 `A` 节点相连的有 `B`、`C` 两个节点，与 `B` 节点相连的有 `A`、`C`、`D` 三个节点，等等。
+
+该无向图的结构如图左所示，其深度优先搜索的遍历路径如图右所示。
 
 ![](https://qcdn.itcharge.cn/images/20211214180351.png)
 
-其对应的动态演示图如下所示。
+其深度优先搜索的遍历过程如下动态图所示。
 
 ![](https://qcdn.itcharge.cn/images/20211214175901.gif)
 
 ## 3. 基于递归实现的深度优先搜索
 
 ### 3.1 基于递归实现的深度优先搜索实现步骤
 
-- `graph` 为存储无向图的字典变量，`visited` 为标记访问节点的 set 集合变量。`start` 为当前遍历边的开始节点。`def dfs_recursive(graph, start, visited):` 为递归实现的深度优先搜索方法。
-- 将 `start` 标记为已访问，即将 `start` 节点放入 `visited` 中（`visited.add(start)`）。
-- 访问节点 `start`，并对节点进行相关操作（看具体题目要求）。
-- 遍历与节点 `start` 相连并构成边的节点 `end`。
-  - 如果 `end` 没有被访问过，则从 `end` 节点调用递归实现的深度优先搜索方法，即 `dfs_recursive(graph, end, visited)`。
+1. 定义 `graph` 为存储无向图的字典变量，`visited` 为标记访问节点的 set 集合变量。`start` 为当前遍历边的开始节点。`def dfs_recursive(graph, start, visited):` 为递归实现的深度优先搜索方法。
+2. 将 `start` 标记为已访问，即将 `start` 节点放入 `visited` 中（`visited.add(start)`）。
+3. 访问节点 `start`，并对节点进行相关操作（看具体题目要求）。
+4. 遍历与节点 `start` 相连并构成边的节点 `end`。
+   1. 如果 `end` 没有被访问过，则从 `end` 节点调用递归实现的深度优先搜索方法，即 `dfs_recursive(graph, end, visited)`。
 
 ### 3.2 基于递归实现的深度优先搜索实现代码
 
@@ -112,31 +114,55 @@ def dfs_stack(graph, start):
 
 #### 5.1.2 题目大意
 
-给定一个由 `1`（陆地）和 `0`（水）组成的的二维网格 `grid`。
+**描述**：给定一个由字符 `'1'`（陆地）和字符 `'0'`（水）组成的的二维网格 `grid`。
 
-要求：计算网格中岛屿的数量。
+**要求**：计算网格中岛屿的数量。
 
-注意：
+**说明**：
 
-- 岛屿总是被水包围，并且每座岛屿只能由水平方向 / 竖直方向上相邻的陆地连接形成。
+- 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
 - 此外，你可以假设该网格的四条边均被水包围。
+- $m == grid.length$。
+- $n == grid[i].length$。
+- $1 \le m, n \le 300$。
+- `grid[i][j]` 的值为 `'0'` 或 `'1'`。
+
+**示例**：
+
+```Python
+输入：grid = [
+  ["1","1","1","1","0"],
+  ["1","1","0","1","0"],
+  ["1","1","0","0","0"],
+  ["0","0","0","0","0"]
+]
+输出：1
+
+
+输入：grid = [
+  ["1","1","0","0","0"],
+  ["1","1","0","0","0"],
+  ["0","0","1","0","0"],
+  ["0","0","0","1","1"]
+]
+输出：3
+```
 
 #### 5.1.3 解题思路
 
-如果把上下左右相邻的字符 `1` 看做是 `1` 个连通块，这道题的目的就是求解一共有多少个连通块。我们可以使用深度优先搜索来做。具体做法如下：
+如果把上下左右相邻的字符 `'1'` 看做是 `1` 个连通块，这道题的目的就是求解一共有多少个连通块。
+
+使用深度优先搜索或者广度优先搜索都可以。
 
-- 使用变量 `count` 统计连通块数目。然后遍历 `grid`。
-- 对于 `(i, j)` 位置上的元素：
-  - 如果 `grid[i][j] == 1`，调用深度优先搜索方法，令统计变量 + 1。
-- 深度优先搜索方法：初始位置 `(i, j)` 位置是一块岛屿，目的是找到该点的岛屿边界。
-  - 将其置为 `0`（避免重复搜索）。然后从该点出发，递归遍历上、下、左、右四个方向，也就是递归遍历 `(i - 1, j)`、`(i, j - 1)`、`(i + 1, j)`、`(i, j + 1)` 四个方向。
-  - 终止条件：
-    - `(i, j)` 超出矩阵范围。
-    -  `(i, j)` 位置上是水，即 `grid[i][j] == 0`。
+##### 思路 1：深度优先搜索
 
-- 最终统计出来的连通块数 `count` 就是我们要求的岛屿数量。
+1. 遍历 `grid` 。
+2. 对于每一个字符为 `'1'` 的元素，遍历其上下左右四个方向，并将该字符置为 `0`，保证下次不会被重复遍历。
+3. 如果超出边界，则返回 `0`。
+4. 对于 `(i, j)` 位置的元素来说，递归遍历的位置就是 `(i - 1, j)`、`(i, j - 1)`、`(i + 1, j)`、`(i, j + 1)` 四个方向。每次遍历到底，统计数记录一次。
+5. 最终统计出深度优先搜索的次数就是我们要求的岛屿数量。
 
-#### 5.1.4 代码
+##### 思路 1：代码
 
 ```Python
 class Solution:
@@ -146,10 +172,10 @@ class Solution:
         if i < 0 or i >= n or j < 0 or j >= m or grid[i][j] == '0':
             return 0
         grid[i][j] = '0'
-        self.dfs(grid, i+1, j)
-        self.dfs(grid, i, j+1)
-        self.dfs(grid, i-1, j)
-        self.dfs(grid, i, j-1)
+        self.dfs(grid, i + 1, j)
+        self.dfs(grid, i, j + 1)
+        self.dfs(grid, i - 1, j)
+        self.dfs(grid, i, j - 1)
 
     def numIslands(self, grid: List[List[str]]) -> int:
         count = 0
@@ -161,6 +187,11 @@ class Solution:
         return count
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(m \times n)$。其中 $m$ 和 $n$ 分别为行数和列数。
+- **空间复杂度**：$O(m \times n)$。
+
 ### 5.2 克隆图
 
 #### 5.2.1 题目链接
@@ -169,45 +200,82 @@ class Solution:
 
 #### 5.2.2 题目大意
 
-给定一个无向连通图中一个节点的引用。
+**描述**：以每个节点的邻接列表形式（二维列表）给定一个无向连通图，其中 `adjList[i]` 表示值为 `i + 1`的节点的邻接列表，`adjList[i][j]` 表示值为 `i + 1` 的节点与值为 `adjList[i][j]` 的节点有一条边。
 
-要求：返回该图的深拷贝。
+**要求**：返回该图的深拷贝。
 
-#### 5.2.3 解题思路
+**说明**：
 
-深拷贝的意思就是构建一张与原图结构、值均一样的图，但是所用的节点不再是原图节点的引用，即每个节点都要新建。
+- 节点数不超过 `100`。
+- 每个节点值 $Node.val$ 都是唯一的，$1 \le Node.val \le 100$。
+- 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
+- 由于图是无向的，如果节点 `p` 是节点 `q` 的邻居，那么节点 `q` 也必须是节点 `p` 的邻居。
+- 图是连通图，你可以从给定节点访问到所有节点。
 
-可以使用深度优先搜索遍历图的所有节点，并在遍历图的同时新建节点，并构建新图。具体做法如下：
+**示例**：
 
-- 使用字典变量 `visited` 存储访问过的节点，键值对为 `原节点 : 新节点`。
-- 从 `node` 节点开始，调用深度优先搜索方法。
-  - 如果 `node` 节点在 `visited` 中，则返回 `visited` 中存储的新节点，即 `visited[node]`。
-  - 新建复制节点 `clone_node`，赋值为 `node.val`。
-  - 将其加入到 `visited` 中，即 `visited[node] = clone_node`。
-  - 遍历 `node` 节点的相邻节点，并从相邻节点开始，递归调用深度优先搜索方法。
-  - 最后返回 `clone_node`。
+![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/133_clone_graph_question.png)
 
-#### 5.2.4 代码
+```Python
+输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
+输出：[[2,4],[1,3],[2,4],[1,3]]
+解释：
+图中有 4 个节点。
+节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
+节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
+节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
+节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
+```
+
+![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/graph-1.png)
 
 ```Python
-class Solution:
-    def dfs(self, node: 'Node', visited) -> 'Node':
-        if node in visited:
-            return visited[node]
+输入：adjList = [[2],[1]]
+输出：[[2],[1]]
+```
 
-        clone_node = Node(node.val, [])
-        visited[node] = clone_node
-        for neighbor in node.neighbors:
-            clone_node.neighbors.append(self.dfs(neighbor, visited))
-        return clone_node
+#### 5.2.3 解题思路
+
+所谓深拷贝，就是构建一张与原图结构、值均一样的图，但是所用的节点不再是原图节点的引用，即每个节点都要新建。
+
+可以用深度优先搜索或者广度优先搜索来做。
+
+##### 思路 1：深度优先搜索
 
+1. 使用哈希表 `visitedDict` 来存储原图中被访问过的节点和克隆图中对应节点，键值对为 原图被访问过的节点：克隆图中对应节点。
+2. 从给定节点开始，以深度优先搜索的方式遍历原图。
+   1. 如果当前节点被访问过，则返回隆图中对应节点。
+   2. 如果当前节点没有被访问过，则创建一个新的节点，并保存在哈希表中。
+   3. 遍历当前节点的邻接节点列表，递归调用当前节点的邻接节点，并将其放入克隆图中对应节点。
+3. 递归结束，返回克隆节点。
+
+##### 思路 1：代码
+
+```Python
+class Solution:
     def cloneGraph(self, node: 'Node') -> 'Node':
         if not node:
             return node
-        visited = dict()
-        return self.dfs(node, visited)
+        visitedDict = dict()
+
+        def dfs(node: 'Node') -> 'Node':
+            if node in visitedDict:
+                return visitedDict[node]
+
+            clone_node = Node(node.val, [])
+            visitedDict[node] = clone_node
+            for neighbor in node.neighbors:
+                clone_node.neighbors.append(dfs(neighbor))
+            return clone_node
+
+        return dfs(node)
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$。其中 $n$ 为图中节点数量。
+- **空间复杂度**：$O(n)$。
+
 ## 参考资料
 
 - 【文章】[深度优先搜索 - LeetBook - 力扣（LeetCode）](https://leetcode.cn/leetbook/read/dfs/egx6xc/)
