# Python solution with detailed explanation

• Solution

Clone Graph https://leetcode.com/problems/clone-graph/

• Add to cache (if not present) when you first visit a neighbor and then enqueue.
``````from collections import deque
class Solution:
# @param node, a undirected graph node
# @return a undirected graph node
def cloneGraph(self, node):
if node is None:
return None
dq = deque()
dq.append(node)
cache = {node:UndirectedGraphNode(node.label)}
while len(dq):
for _ in range(len(dq)):
x = dq.popleft()
for nbr in x.neighbors:
if nbr not in cache:
cache[nbr] = UndirectedGraphNode(nbr.label)
dq.append(nbr)
cache[x].neighbors.append(cache[nbr])
return cache[node]
``````

Depth First based copy

• Simple recursive algorithm to copy with a dictionary
``````class Solution:
def helper(self, node, cache):
if node is None:
return None
elif node in cache:
return cache[node]
else:
cache[node] = UndirectedGraphNode(node.label)
for x in node.neighbors:
cache[node].neighbors.append(self.helper(x, cache))
return cache[node]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.