5
5
6
6
## 题目大意
7
7
8
- 给定一个无向连通图中一个节点的引用 。
8
+ ** 描述 ** :以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 ` adjList[i] ` 表示值为 ` i + 1 ` 的节点的邻接列表, ` adjList[i][j] ` 表示值为 ` i + 1 ` 的节点与值为 ` adjList[i][j] ` 的节点有一条边 。
9
9
10
- 要求:返回该图的深拷贝。
10
+ ** 要求** :返回该图的深拷贝。
11
+
12
+ ** 说明** :
13
+
14
+ - 节点数不超过 ` 100 ` 。
15
+ - 每个节点值 $Node.val$ 都是唯一的,$1 \le Node.val \le 100$。
16
+ - 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
17
+ - 由于图是无向的,如果节点 ` p ` 是节点 ` q ` 的邻居,那么节点 ` q ` 也必须是节点 ` p ` 的邻居。
18
+ - 图是连通图,你可以从给定节点访问到所有节点。
19
+
20
+ ** 示例** :
21
+
22
+ ![ ] ( https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/133_clone_graph_question.png )
23
+
24
+ ``` Python
25
+ 输入:adjList = [[2 ,4 ],[1 ,3 ],[2 ,4 ],[1 ,3 ]]
26
+ 输出:[[2 ,4 ],[1 ,3 ],[2 ,4 ],[1 ,3 ]]
27
+ 解释:
28
+ 图中有 4 个节点。
29
+ 节点 1 的值是 1 ,它有两个邻居:节点 2 和 4 。
30
+ 节点 2 的值是 2 ,它有两个邻居:节点 1 和 3 。
31
+ 节点 3 的值是 3 ,它有两个邻居:节点 2 和 4 。
32
+ 节点 4 的值是 4 ,它有两个邻居:节点 1 和 3 。
33
+ ```
34
+
35
+ ![ ] ( https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/02/01/graph-1.png )
36
+
37
+ ``` Python
38
+ 输入:adjList = [[2 ],[1 ]]
39
+ 输出:[[2 ],[1 ]]
40
+ ```
11
41
12
42
## 解题思路
13
43
14
44
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
15
45
16
46
可以用深度优先搜索或者广度优先搜索来做。
17
47
18
- 以深度优先搜索为例,根据所给定的节点,以深度优先搜索的方式遍历图,并在遍历图的同时,进行新建节点,并构建新图。
48
+ ### 思路 1:深度优先搜索
19
49
20
- ## 代码
50
+ 1 . 使用哈希表 ` visitedDict ` 来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。
51
+ 2 . 从给定节点开始,以深度优先搜索的方式遍历原图。
52
+ 1 . 如果当前节点被访问过,则返回隆图中对应节点。
53
+ 2 . 如果当前节点没有被访问过,则创建一个新的节点,并保存在哈希表中。
54
+ 3 . 遍历当前节点的邻接节点列表,递归调用当前节点的邻接节点,并将其放入克隆图中对应节点。
55
+ 3 . 递归结束,返回克隆节点。
56
+
57
+ ### 思路 1:代码
21
58
22
59
``` Python
23
60
class Solution :
@@ -39,3 +76,8 @@ class Solution:
39
76
return dfs(node)
40
77
```
41
78
79
+ ### 思路 1:复杂度分析
80
+
81
+ - ** 时间复杂度** :$O(n)$。其中 $n$ 为图中节点数量。
82
+ - ** 空间复杂度** :$O(n)$。
83
+
0 commit comments