# Question

Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

# Solution

```
# 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
processed_nodes = dict()
new_node = UndirectedGraphNode(node.label)
self.clone(node, new_node, processed_nodes)
return new_node
def clone(self, node, new_node, processed_nodes):
processed_nodes[node.label] = new_node
for neighbor in node.neighbors:
if neighbor.label in processed_nodes:
new_node.neighbors.append(processed_nodes[neighbor.label])
else:
new_neighbor = UndirectedGraphNode(neighbor.label)
new_node.neighbors.append(new_neighbor)
self.clone(neighbor, new_neighbor, processed_nodes)
```