Update 03.Graph-BFS.md

itcharge · itcharge · commit 6763734b6d88 · 2022-09-08T16:00:05.000+08:00
diff --git a/Contents/08.Graph/02.Graph-Traversal/03.Graph-BFS.md b/Contents/08.Graph/02.Graph-Traversal/03.Graph-BFS.md
@@ -1,5 +1,3 @@
-
-
 ## 1. 广度优先搜索简介
 
 > **广度优先搜索算法**（Breadth First Search）：简称为 BFS，又译作宽度优先搜索 / 横向优先搜索。是一种用于遍历或搜索树或图的算法。该算法从根节点开始，沿着树的宽度遍历树或图的节点。如果所有节点均被访问，则算法中止。
@@ -24,110 +22,137 @@ graph = {
 }
 ```
 
-该无向图的结构如图左所示，图右为宽度优先搜索的遍历路径。
+该无向图对应的邻接字典表示：无向图中有 `A`、`B`、`C`、`D`、`E`、`F` 共 `6` 个节点，其中与 `A` 节点相连的有 `B`、`C` 两个节点，与 `B` 节点相连的有 `A`、`C`、`D` 三个节点，等等。
+
+该无向图的结构如图左所示，其宽度优先搜索的遍历路径如图右所示。
 
 ![](https://qcdn.itcharge.cn/images/20220105135253.png)
 
-其对应的动态演示图如下所示。
+其广度优先搜索的遍历过程如下动图所示。
 
 ![](https://qcdn.itcharge.cn/images/20220105175535.gif)
 
 ## 3. 基于队列实现的广度优先搜索
 
 ### 3.1 基于队列实现的广度优先搜索实现步骤
 
-1. `graph` 为存储无向图的字典变量，`start` 为开始节点。
-1. 然后定义 `visited` 为标记访问节点的 set 集合变量。定义 `q` 为存放节点的队列。
-1. 首先将起始节点放入队列 `q`中，即 `q.put(start)`。并将其标记为访问，即 `visited.add(start)`。
+1. 定义 `graph` 为存储无向图的字典变量，`start` 为开始节点，`def bfs(graph, start):` 为队列实现的广度优先搜索方法。
+2. 定义 `visited` 为标记访问节点的 set 集合变量，`queue` 为存放节点的队列。
+3. 首先将起始节点标记为访问，即 `visited.add(start)`。并将其放入队列 `queue`中，即 `queue.append(start)`。
 4. 从队列中取出第一个节点 `node_u`。访问节点 `node_u`，并对节点进行相关操作（看具体题目要求）。
-2. 遍历与节点 `node_u` 相连并构成边的节点 `node_v`。
-   - 如果 `node_v` 没有被访问过，则将 `node_v` 节点放入队列中，并标记访问，即 `q.append(node_v)`，`visited.add(node_v)`。
-6. 重复步骤 4 ~ 5，直到 `q` 为空。
+5. 遍历与节点 `node_u` 相连并构成边的节点 `node_v`。
+   - 如果 `node_v` 没有被访问过（即 `node_v` 不在 `visited` 中）：则将 `node_v` 节点放入队列中，并标记访问，即 `q.append(node_v)`，`visited.add(node_v)`。
+6. 重复步骤 4 ~ 5，直到队列 `queue` 为空。
 
 ### 3.2 基于队列实现的广度优先搜索实现代码
 
 ```Python
 import collections
 
 def bfs(graph, start):
-    visited = set(start)
-    q = collections.deque([start])
+    visited = set()
+    queue = collections.deque([])
+    
+    visited.add(start)
+    queue.append(start)
     
-    while q:
-        node_u = q.popleft()
+    while queue:
+        node_u = queue.popleft()
         print(node_u)
         for node_v in graph[node_u]:
             if node_v not in visited:
                 visited.add(node_v)
-                q.append(node_v)
+                queue.append(node_v)
 ```
 
 ## 4. 广度优先搜索应用
 
-### 4.1 无向图中连通分量的数目
+### 4.1 克隆图
 
 #### 4.1.1 题目链接
 
-- [323. 无向图中连通分量的数目 - 力扣（LeetCode）](https://leetcode.cn/problems/number-of-connected-components-in-an-undirected-graph/)
+- [133. 克隆图 - 力扣（LeetCode）](https://leetcode.cn/problems/clone-graph/)
 
 #### 4.1.2 题目大意
 
-给定 `n` 个节点（编号从 `0` 到 `n - 1`）的图的无向边列表 `edges`，其中 `edges[i] = [u, v]` 表示节点 `u` 和节点 `v` 之间有一条无向边。
+**描述**：以每个节点的邻接列表形式（二维列表）给定一个无向连通图，其中 `adjList[i]` 表示值为 `i + 1`的节点的邻接列表，`adjList[i][j]` 表示值为 `i + 1` 的节点与值为 `adjList[i][j]` 的节点有一条边。
 
-要求：计算该无向图中连通分量的数量。
+**要求**：返回该图的深拷贝。
 
-#### 4.1.3 解题思路
+**说明**：
 
-先来看一下图论中相关的名次解释。
+- 节点数不超过 `100`。
+- 每个节点值 $Node.val$ 都是唯一的，$1 \le Node.val \le 100$。
+- 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
+- 由于图是无向的，如果节点 `p` 是节点 `q` 的邻居，那么节点 `q` 也必须是节点 `p` 的邻居。
+- 图是连通图，你可以从给定节点访问到所有节点。
 
-- 连通图：在无向图中，如果可以从顶点 $v_i$ 到达 $v_j$，则称 $v_i$ 和 $v_j$ 连通。如果图中任意两个顶点之间都连通，则称该图为连通图。
-- 无向图的连通分量：如果该图为连通图，则连通分量为本身；否则将无向图中的极大连通子图称为连通分量，每个连通分量都是一个连通图。
-- 无向图的连通分量个数：无向图的极大连通子图的个数。
+**示例**：
 
-接下来我们来解决这道题。
+![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/133_clone_graph_question.png)
 
-由于题目给定的是无向边列表。我们先将其转变为邻接表的形式。然后使用广度优先搜索计算联通分量的个数。具体做法如下：
+```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 。
+```
 
-- 使用变量 `count` 记录连通分量个数。使用集合变量 `visited` 记录访问过的节点，使用邻接表 `graph` 记录图结构。
-- 从 `0` 开始，依次遍历 `n` 个节点。
-- 如果第 `i` 个节点未访问过：
-  - 将其添加到 `visited` 中。
-  - 并且连通分量个数累加，即 `count += 1`。
-  - 定义一个队列 `q`，将第 `i` 个节点加入到队列中。
-  - 从队列中取出第一个节点，遍历与其链接的节点，并将未遍历过的节点加入到队列 `q` 和 `visited` 中。
-  - 直到队列为空，则继续向后遍历。
+![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/graph-1.png)
 
-- 最后输出连通分量数目 `count`。
+```Python
+输入：adjList = [[2],[1]]
+输出：[[2],[1]]
+```
+
+#### 4.1.3 解题思路
 
-#### 4.1.4 代码
+##### 思路 1：广度优先搜索
 
-```Python
-import collections
+1. 使用哈希表 `visited` 来存储原图中被访问过的节点和克隆图中对应节点，键值对为 原图被访问过的节点：克隆图中对应节点。使用队列`queue` 存放节点。
+2. 根据起始节点，创建一个新的节点，并将其添加到哈希表 `visited` 中，即 `visited[node] = Node(node.val, [])`。然后将起始节点放入队列 `queue`中，即 `queue.append(node)`。
+3. 从队列中取出第一个节点 `node_u`。访问节点 `node_u`。
+4. 遍历与节点 `node_u` 相连并构成边的节点 `node_v`。
+   1. 如果 `node_v` 没有被访问过（即 `node_v` 不在 `visited` 中）：
+      1. 则根据 `node_v` 创建一个新的节点，并将其添加到哈希表 `visited` 中，即 `visited[node_v] = Node(node_v.val, [])`。
+      2. 然后将 `node_v` 节点放入队列 `queue` 中，即 `queue.append(node_v)`。
+5. 重复步骤 3 ~ 4，直到队列 `queue` 为空。
+6. 广度优先搜索结束，返回起始节点的克隆节点（即 `visited[node]`）。
 
+##### 思路 1：代码
+
+```Python
 class Solution:
-    def countComponents(self, n: int, edges: List[List[int]]) -> int:
-        count = 0
-        visited = set()
-        graph = [[] for _ in range(n)]
-
-        for x, y in edges:
-            graph[x].append(y)
-            graph[y].append(x)
-
-        for i in range(n):
-            if i not in visited:
-                visited.add(i)
-                count += 1
-                q = collections.deque([i])
-                while q:
-                    node_u = q.popleft()
-                    for node_v in graph[node_u]:
-                        if node_v not in visited:
-                            visited.add(node_v)
-                            q.append(node_v)
-        return count
+    def cloneGraph(self, node: 'Node') -> 'Node':
+        if not node:
+            return node
+        
+        visited = dict()
+        queue = collections.deque()
+
+        visited[node] = Node(node.val, [])
+        queue.append(node)
+
+        while queue:
+            node_u = queue.popleft()
+            for node_v in node_u.neighbors:
+                if node_v not in visited:
+                    visited[node_v] = Node(node_v.val, [])
+                    queue.append(node_v)
+                visited[node_u].neighbors.append(visited[node_v])
+        
+        return visited[node]
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$。其中 $n$ 为图中节点数量。
+- **空间复杂度**：$O(n)$。
+
 ### 4.2 岛屿的最大面积
 
 #### 4.2.1 题目链接
@@ -136,19 +161,34 @@ class Solution:
 
 #### 4.2.2 题目大意
 
-给定一个只包含 `0`、`1` 元素的二维数组 `grid`，其中 `1` 代表岛屿，`0` 代表水。一座岛的面积就是上下左右相邻的 `1` 所组成的连通块的数目。
+**描述**：给定一个只包含 `0`、`1` 元素的二维数组，`1` 代表岛屿，`0` 代表水。一座岛的面积就是上下左右相邻的 `1` 所组成的连通块的数目。
+
+**要求**：计算出最大的岛屿面积。
+
+**说明**：
 
-要求：计算出最大的岛屿面积。
+- $m == grid.length$。
+- $n == grid[i].length$。
+- $1 \le m, n \le 50$。
+- $grid[i][j]$ 为 `0` 或 `1`。
 
-示例 ：
+**示例**：
 
-![img](https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg)
+![](https://assets.leetcode.com/uploads/2021/05/01/maxarea1-grid.jpg)
 
-图中最大的岛屿面积为 6。
+```Python
+输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
+输出：6
+解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
+
+
+输入：grid = [[0,0,0,0,0,0,0,0]]
+输出：0
+```
 
 #### 4.2.3 解题思路
 
-使用广度优先搜索方法。具体做法如下：
+##### 思路 1：广度优先搜索
 
 1. 使用 `ans` 记录最大岛屿面积。
 2. 遍历二维数组的每一个元素，对于每个值为 `1` 的元素：
@@ -157,7 +197,7 @@ class Solution:
    3. 不断重复上一步骤，直到队列 `q` 为空。
    4. 更新当前最大岛屿面积，即 `ans = max(ans, temp_ans)`。
 
-#### 4.2.4 代码
+##### 思路 1：代码
 
 ```Python
 import collections
@@ -188,6 +228,11 @@ class Solution:
         return ans
 ```
 
+##### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n \times m)$，其中 $m$ 和 $n$ 分别为行数和列数。
+- **空间复杂度**：$O(n \times m)$。
+
 ## 参考资料
 
 - 【文章】[广度优先搜索 - LeetBook - 力扣（LeetCode）](https://leetcode.cn/leetbook/read/bfs/e69rh1/)
