# LeetCode 133Clone Graph

## LeetCode 133 Clone Graph Problem

``````# Definition for a undirected graph node
# class UndirectedGraphNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution(object):

# def __init__(self):
#     self.label_map = {}

# def cloneGraph(self, node):
#     """
#     :type node: UndirectedGraphNode
#     :rtype: UndirectedGraphNode
#     """
#     # DFS
#     if node is None:
#         return None
#     res = UndirectedGraphNode(node.label)
#     self.label_map[node.label] = res
#     for ne in node.neighbors:
#         if ne.label not in self.label_map:
#             res.neighbors.append(self.cloneGraph(ne))
#         else:
#             res.neighbors.append(self.label_map[ne.label])
#     return res

def cloneGraph(self, node):
# BFS
if node is None:
return None
label_map = {}
queue = [node]
graphCopy = UndirectedGraphNode(node.label)
label_map[node.label] = graphCopy
while len(queue) > 0:
curr = queue.pop(0)
for ne in curr.neighbors:
if ne.label in label_map:
label_map[curr.label].neighbors.append(label_map[ne.label])
else:
neighborCopy = UndirectedGraphNode(ne.label)
label_map[curr.label].neighbors.append(neighborCopy)
label_map[ne.label] = neighborCopy
queue.append(ne)
return graphCopy

``````
Download Clone Graph.py

## List of all Clone Graph problems

Leetcode 133 Clone Graph problem solution in python3 with explanation. This is the best place to expand your knowledge and get prepared for your next interview.

Feedback is the most important part of any website.

If you have any query, suggestion or feedback, Please feel free to contact us.