DFS,克隆图就是要返回图的深拷贝，所以我们要新建一个一模一样的图
所以需要对图进行遍历，和多叉树一样，先遍历根节点，如果是新的节点没有遇到过，我们就新建一个一样的节点
之后用一个哈希表进行标记，访问过这个节点了说明已经建好了，下次如果出现在哈希表中的节点就不需要再新建了
因为节点类还包含他的邻居节点列表，所以遍历它的邻居，将新建节点的邻居节点也建立出来并加入列表，同样，如果建立过
这个节点，说明这个节点已经是新的了，直接返回就行。
def cloneGraph(self, node):
"""
:type node: Node
:rtype: Node
"""
self.visited = {}
def dfs(node):
if not node: #没有节点返回
return node
if node in self.visited: #建过了，直接加入到邻居节点
return self.visited[node]
self.visited[node] = Node(node.val,[]) #没建过，先建立
for n in node.neighbors:
self.visited[node].neighbors.append(dfs(n))
return self.visited[node]
return dfs(node)
BFS一样
def cloneGraph(self, node):
"""
:type node: Node
:rtype: Node
"""
if not node:
return node
queue = deque([node])
visited = {}
visited[node] = Node(node.val,[]) #记录是否是新建的
while queue:
n = queue.popleft()
for neighbor in n.neighbors:
if neighbor not in visited: #如果没建立这个节点
visited[neighbor] = Node(neighbor.val,[]) #先建立
queue.append(neighbor) #放入队列，以便后序建立它的邻居节点
visited[n].neighbors.append(visited[neighbor]) #由于上面的if判断语句，这里加的邻居节点一定是新建的
return visited[node
]
