Clone Graph

Question

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

Thoughts

BFS

用hashmap来存储已经copy过的node

for the first node, put it into a queue, and make a copy of it, put them into hashmap

when we encounter a node, get the copy of this node, check its neighbors, loop through the neighbors

if the neighbor is already copied:
    #already visited 
    get the copy from hashmap
    put it into curr copy's neighbors
else:
    #haven't visited
    make a copy
    add into curr copy's neighbors
    put into hashmap
    #haven't visited, so push into queue for visit
    append into queue

Solution

from collections import deque
# Definition for a undirected graph node
# class UndirectedGraphNode:
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.dict = {}

    def cloneGraph(self, node):
        if not node:
            return None
        #queue
        queue = deque()
        queue.append(node)
        #new node and put into map
        newNode = UndirectedGraphNode(node.label)
        self.dict[node] = newNode
        while queue:
            curr = queue.popleft()
            copiedCurr = self.dict[curr]
            for n in curr.neighbors:
                if n in self.dict:
                    copiedNode = self.dict[n]
                    copiedCurr.neighbors.append(copiedNode)
                else:
                    copyNode = UndirectedGraphNode(n.label)
                    copiedCurr.neighbors.append(copyNode)
                    self.dict[n] = copyNode
                    queue.append(n)
        return newNode