Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:
{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:
Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

  1. The number of nodes will be between 1 and 100.
  2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
  3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
  4. You must return the copy of the given node as a reference to the cloned graph.

Solutions

  不管使用dfs还是bfs都需要一个哈希表map来存储原图中的节点和新图中的节点的一一映射。map的作用在于替代bfs和dfs中的visit数组,一旦map中出现了映射关系,就说明已经复制完成,也就是已经访问过了。

1. DFS

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return None
        return self.dfs(node, {})
    
    def dfs(self, node, map_):
        if node in map_:
            return map_[node]
        o_node = Node(node.val, [])
        map_[node] = o_node
        for neighbor in node.neighbors:
            o_node.neighbors.append(self.dfs(neighbor, map_))
        return o_node
# Runtime: 56 ms, faster than 71.42% of Python online submissions for Clone Graph.
# Memory Usage: 12.8 MB, less than 68.75% of Python online submissions for Clone Graph.

2. BFS

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: Node
        :rtype: Node
        """
        if not node:
            return None
        queue = collections.deque()
        queue.append(node)
        map_ = {}
        res_node = Node(node.val, [])
        map_[node] = res_node
        while queue:
            cur_node = queue.popleft()
            if not cur_node:
                continue
            for neighbor in cur_node.neighbors:
                if neighbor not in map_:
                    map_[neighbor] = Node(neighbor.val, [])
                    queue.append(neighbor)
                map_[cur_node].neighbors.append(map_[neighbor])
        return res_node
# Runtime: 60 ms, faster than 39.95% of Python online submissions for Clone Graph.
# Memory Usage: 12.8 MB, less than 31.25% of Python online submissions for Clone Graph.

References

  1. 133. Clone Graph
  2. Clone Graph @ Python
  3. 133. Clone Graph 解题报告