Skip to content

Commit 0a35bb2

Browse files
committed
Update 0133. 克隆图.md
1 parent 7fe41c8 commit 0a35bb2

File tree

1 file changed

+46
-4
lines changed

1 file changed

+46
-4
lines changed

Solutions/0133. 克隆图.md

Lines changed: 46 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -5,19 +5,56 @@
55

66
## 题目大意
77

8-
给定一个无向连通图中一个节点的引用
8+
**描述**:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 `adjList[i]` 表示值为 `i + 1`的节点的邻接列表,`adjList[i][j]` 表示值为 `i + 1` 的节点与值为 `adjList[i][j]` 的节点有一条边
99

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,它有两个邻居:节点 24
30+
节点 2 的值是 2,它有两个邻居:节点 13
31+
节点 3 的值是 3,它有两个邻居:节点 24
32+
节点 4 的值是 4,它有两个邻居:节点 13
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+
```
1141

1242
## 解题思路
1343

1444
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
1545

1646
可以用深度优先搜索或者广度优先搜索来做。
1747

18-
以深度优先搜索为例,根据所给定的节点,以深度优先搜索的方式遍历图,并在遍历图的同时,进行新建节点,并构建新图。
48+
### 思路 1:深度优先搜索
1949

20-
## 代码
50+
1. 使用哈希表 `visitedDict` 来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。
51+
2. 从给定节点开始,以深度优先搜索的方式遍历原图。
52+
1. 如果当前节点被访问过,则返回隆图中对应节点。
53+
2. 如果当前节点没有被访问过,则创建一个新的节点,并保存在哈希表中。
54+
3. 遍历当前节点的邻接节点列表,递归调用当前节点的邻接节点,并将其放入克隆图中对应节点。
55+
3. 递归结束,返回克隆节点。
56+
57+
### 思路 1:代码
2158

2259
```Python
2360
class Solution:
@@ -39,3 +76,8 @@ class Solution:
3976
return dfs(node)
4077
```
4178

79+
### 思路 1:复杂度分析
80+
81+
- **时间复杂度**:$O(n)$。其中 $n$ 为图中节点数量。
82+
- **空间复杂度**:$O(n)$。
83+

0 commit comments

Comments
 (0)