Clone Graph

https://leetcode.com/problems/clone-graph/description/

1. BFS (using deque)

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

from collections import deque
class Solution:
    # @param node, a undirected graph node
    # @return a undirected graph node
    def __init__(self):
        self.visited = {}

    def cloneGraph(self, node):
        if not node:
            return None

        queue = deque([node])
        root = UndirectedGraphNode(node.label)
        self.visited[node] = root

        while queue:

            select = queue.popleft()
            for neighbor in select.neighbors:
                if not neighbor in self.visited:
                    new_node = UndirectedGraphNode(neighbor.label)
                    self.visited[neighbor] = new_node
                    queue.append(neighbor)

                self.visited[select].neighbors.append(self.visited[neighbor])    

        return root

1. DFS (recursive)

# 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.hashmap = {}

    def cloneGraph(self, node):
        if not node:
            return None

        clone = UndirectedGraphNode(node.label)
        self.hashmap[node] = clone

        for each in node.neighbors:
            if not each in self.hashmap:
                clone.neighbors.append(self.cloneGraph(each))
            else:
                clone.neighbors.append(self.hashmap[each])

        return clone