0133. 克隆图 #
- 标签:深度优先搜索、广度优先搜索、图、哈希表
- 难度:中等
题目大意 #
描述:以每个节点的邻接列表形式(二维列表)给定一个无向连通图,其中 adjList[i]
表示值为 i + 1
的节点的邻接列表,adjList[i][j]
表示值为 i + 1
的节点与值为 adjList[i][j]
的节点有一条边。
要求:返回该图的深拷贝。
说明:
- 节点数不超过
100
。 - 每个节点值 $Node.val$ 都是唯一的,$1 \le Node.val \le 100$。
- 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
- 由于图是无向的,如果节点
p
是节点q
的邻居,那么节点q
也必须是节点p
的邻居。 - 图是连通图,你可以从给定节点访问到所有节点。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
所谓深拷贝,就是构建一张与原图结构、值均一样的图,但是所用的节点不再是原图节点的引用,即每个节点都要新建。
可以用深度优先搜索或者广度优先搜索来做。
思路 1:深度优先搜索 #
- 使用哈希表
visited
来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。 - 从给定节点开始,以深度优先搜索的方式遍历原图。
- 如果当前节点被访问过,则返回隆图中对应节点。
- 如果当前节点没有被访问过,则创建一个新的节点,并保存在哈希表中。
- 遍历当前节点的邻接节点列表,递归调用当前节点的邻接节点,并将其放入克隆图中对应节点。
- 递归结束,返回克隆节点。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 为图中节点数量。
- 空间复杂度:$O(n)$。
思路 2:广度优先搜索 #
- 使用哈希表
visited
来存储原图中被访问过的节点和克隆图中对应节点,键值对为 原图被访问过的节点:克隆图中对应节点。使用队列queue
存放节点。 - 根据起始节点,创建一个新的节点,并将其添加到哈希表
visited
中,即visited[node] = Node(node.val, [])
。然后将起始节点放入队列queue
中,即queue.append(node)
。 - 从队列中取出第一个节点
node_u
。访问节点node_u
。 - 遍历与节点
node_u
相连并构成边的节点node_v
。- 如果
node_v
没有被访问过(即node_v
不在visited
中):- 则根据
node_v
创建一个新的节点,并将其添加到哈希表visited
中,即visited[node_v] = Node(node_v.val, [])
。 - 然后将
node_v
节点放入队列queue
中,即queue.append(node_v)
。
- 则根据
- 如果
- 重复步骤 3 ~ 4,直到队列
queue
为空。 - 广度优先搜索结束,返回起始节点的克隆节点(即
visited[node]
)。
思路 2:代码 #
|
|
思路 2:复杂度分析 #
- 时间复杂度:$O(n)$。其中 $n$ 为图中节点数量。
- 空间复杂度:$O(n)$。