原题
克隆一张无向图，图中的每个节点包含一个 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
