133-克隆图

Leetcode题解
  1. 133、克隆图
    1. 题目：
    2. 题解：

133、克隆图

https://leetcode-cn.com/problems/clone-graph/

题目：

axAofP.png

题解：

所谓深度克隆图，就是对图中每一个节点都new出来，而不是引用。因此就需要DFS深度遍历，此题节点对象中的neighbors是邻接矩阵，对于无向图来说，1——2相连，那么矩阵[0]中有2，矩阵[1]中有1，相当于两个点互相有向指向，因此需要处理重复遍历的问题。所以使用了字典（类似于hashmap），主键是node对象，值是深克隆的node_copy，递归遍历，将第一个点的所有邻居都递归遍历一边后，完成深克隆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        map_ = {}

        def dfs(node):
            if node is None:
                return
            if node in map_:
                return map_[node]
            clone = Node(node.val, [])
            map_[node] = clone
            for i in node.neighbors:
                clone.neighbors.append(dfs(i))
            return clone
        return dfs(node)

当前网速较慢或者你使用的浏览器不支持博客特定功能，请尝试刷新或换用Chrome、Firefox等现代浏览器