题目描述：
Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.
OJ's undirected graph serialization:
Nodes are labeled uniquely.
We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.
As an example, consider the serialized graph {0,1,2#1,2#2,2}.
The graph has a total of three nodes, and therefore contains three parts as separated by #.
First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.
Visually, the graph looks like the following:
1
/ \
/ \
0 --- 2
/ \
\_/
题目大意：
克隆一个无向图。图中的每个节点包含一个标签及其邻居的列表。
OJ对于无向图的序列化：
节点的标签是唯一的。
我们使用 井号（#） 作为节点的分隔符，使用 逗号（，）作为节点标签以及每个邻居之间的分隔符。
例如，考虑下面的序列化图 {0,1,2#1,2#2,2}
上图包含3个节点，因而包含3个#分隔符。
第一个节点标签为0，节点0与节点1，节点2相连。 第二个节点标签为1, 节点1与节点2相连。 第三个节点标签为2，节点2与节点2相连（其本身），因而形成一个自环。
可视化地，上面的图看起来像这样：
1
/ \
/ \
0 --- 2
/ \
\_/
解题思路：
本题考查图的深拷贝
通过BFS或者DFS遍历图，利用字典维护标号与新增节点之间的映射关系。
Python代码：
# 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 cloneGraph(self, node):
if node is None:
return None
needle = UndirectedGraphNode(node.label)
nodeDict = {node.label : needle}
stack = [node]
while stack:
top = stack.pop()
cnode = nodeDict[top.label]
for n in top.neighbors:
if n.label not in nodeDict:
nodeDict[n.label] = UndirectedGraphNode(n.label)
stack.append(n)
cnode.neighbors.append(nodeDict[n.label])
return needle
本文链接：http://bookshadow.com/weblog/2015/08/10/leetcode-clone-graph/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
