# LeetCode Medium 133. Clone Graph

tags: leetcode

問題

• Explore
• Problems

アイデア

｢無向グラフの deepcopy を作成し､返せ｣という問題です｡

BFS､DFSで実装出来ると思いますが､今回はBFSで実装します｡

解法

Queueを使います｡つまりBFSです｡

• 与えられた node を queue に格納します｡
• 今まで通ったオリジナルのノードのコピーを格納する連想配列 copy_of_original を作成します｡
• そして､ queue の中身が空でなければ以下を実行します｡
  • cur は queue の先頭のノードで､このノードの neighbors を全て調べます｡
    • もし､ copy_of_original に入っていなければ､その neighbor を copy_neighbor として neighbor と結びつけます｡そして､グラフの更新をし､最後に neighbor をキューに追加します｡
    • もし､既に入っていれば､ その cur のコピーを作り､ neighborに対応するコピーをその neighbors に追加します｡

計算量

ノードの数を $N$ とします｡

• 時間計算量
  • $O(N)$
• 空間計算量
  • $O(N)$

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return 
        copy_node = Node(node.val, [])
        copy_of_original = {node: copy_node}
        queue = collections.deque([node])
        while queue:
            cur = queue.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in copy_of_original: # neighbor is not visited
                    copy_neighbor = Node(neighbor.val, [])
                    copy_of_original[neighbor] = copy_neighbor
                    copy_of_original[cur].neighbors.append(copy_neighbor)
                    queue.append(neighbor)
                else:
                    copy_of_original[cur].neighbors.append(copy_of_original[neighbor])
        return copy_node