LeetCode 133 [Clone Graph]

原题

克隆一张无向图，图中的每个节点包含一个 label 和一个表 neighbors。
你的程序需要返回一个经过深度拷贝的新图。这个新图和原图具有同样的结构，并且对新图的任何改动不会对原图造成任何影响。

样例
比如，序列化图 {0,1,2#1,2#2,2} 共有三个节点, 因此包含两个个分隔符#。
第一个节点label为0，存在边从节点0链接到节点1和节点2
第二个节点label为1，存在边从节点1连接到节点2
第三个节点label为2，存在边从节点2连接到节点2(本身),从而形成自环。

我们能看到如下的图：

   1
  / \
 /   \
0 --- 2
     / \
     \_/

解题思路

• 首先，要遍历无向图，需要使用Hash Map来当作visited数组，防止重复访问而造成程序中的死循环
• 遍历图有两种方式 - BFS & DFS，本题均可采用
• BFS - 使用Queue (prefer)
• DFS - 递归或者使用Stack，对于DFS，每次clone一个node的时候，就要把它所有的neighbor加入到新clone的node的neighbor中，此时recursivly调用dfs，如果没有visited过 - 新建一个node，否则直接从map中找到返回
• 在visited数组中，key值为原来的node，value为新clone的node，如果一个node不存在于map中，说明这个node还未被clone，将它clone后放入queue中继续处理neighbors

完整代码

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

import Queue

class Solution(object):
    def __init__(self):
        self.visited = {}
        
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return None
            
        newHead = UndirectedGraphNode(node.label)
        self.visited[node] = newHead
        
        myQueue = Queue.Queue()
        myQueue.put(node)
        while myQueue.qsize():
            current = myQueue.get()
            for neighbor in current.neighbors:
                if neighbor not in self.visited:
                    newNode = UndirectedGraphNode(neighbor.label)
                    self.visited[current].neighbors.append(newNode)
                    self.visited[neighbor] = newNode
                    myQueue.put(neighbor)
                else: # turn directed graph to undirected graph
                    self.visited[current].neighbors.append(self.visited[neighbor])
                    
        return newHead

# Method 2: DFS
class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return None
            
        return self.dfs(node, {})
        
    def dfs(self, node, map):
        if node in map:
            return map[node]
        newNode = UndirectedGraphNode(node.label)
        map[node] = newNode
        for neighbor in node.neighbors:
            newNode.neighbors.append(self.dfs(neighbor, map))
            
        return newNode