0133. 克隆图

0133. 克隆图 #

  • 标签:深度优先搜索、广度优先搜索、图
  • 难度:中等

题目大意 #

给定一个无向连通图中一个节点的引用。

要求:返回该图的深拷贝。

解题思路 #

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

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

以深度优先搜索为例,根据所给定的节点,以深度优先搜索的方式遍历图,并在遍历图的同时,进行新建节点,并构建新图。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return node
        visitedDict = dict()

        def dfs(node: 'Node') -> 'Node':
            if node in visitedDict:
                return visitedDict[node]

            clone_node = Node(node.val, [])
            visitedDict[node] = clone_node
            for neighbor in node.neighbors:
                clone_node.neighbors.append(dfs(neighbor))
            return clone_node

        return dfs(node)
本站总访问量  次  |  您是本站第  位访问者