Copy Graph

题目描述

Clone an undirected graph.

Each node in the graph contains a label and a list of its neighbors.

解题方法

这种deep copy的题目一般的做法就是要用到hashmap，先存下old/new的pair，然后在 遍历的时候check是否已经copy过，如果copy过就从hashmap中取出，如果没有就新建一个。

遍历graph的过程是bfs, 用一个queue来implement。

Solution

from collections import deque
# Definition for a undirected graph node
# class UndirectedGraphNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return None

        copiedMap = {}
        queue = deque()
        queue.append(node)
        newNode = UndirectedGraphNode(node.label)
        copiedMap[node] = newNode

        while queue:
            cur = queue.popleft()
            copiedCur = copiedMap[cur]
            for neighbor in cur.neighbors:
                if neighbor in copiedMap:
                    # if already copied, means it should already be visited before
                    # no need to add into queue again
                    copiedN = copiedMap[neighbor]
                    copiedCur.neighbors.append(copiedN)
                else:
                    # first time encounter this node, copy it and add into queue
                    newN = UndirectedGraphNode(neighbor.label)
                    copiedMap[neighbor] = newN
                    queue.append(neighbor)
                    copiedCur.neighbors.append(newN)
        return newNode

Reference