# 133. Clone Graph

Given a graph, return a deep copy of it.

This problem is a graph traversal problem. I used BFS traversal to solve it. It uses the standard algorithm, but with the following changes:

- an extra variable,
`current_clone`

, is used to store the copied node. When the`current_node`

neighbors are traversed the standard check is done to see if the neighbor has been visited or not. If it has not been added then a new Node is created with the value. This is the copied value. In both cases the neighbor is added to the`current_clone`

neighbors list. - The visited hash value stores a copy of a Node. In the standard algorithm it is simply stores True. This hash stores the deep copy values.

"""

# Definition for a Node.

class Node:

def __init__(self, val = 0, neighbors = None):

self.val = val

self.neighbors = neighbors if neighbors is not None else []

"""

class Solution:

def cloneGraph(self, node: 'Node') -> 'Node':

if node is None:

return node

# note to self could also do queue = deque([node]) to condense the following two lines

queue = deque()

queue.append(node)

# note: the visited hash creates a new Node as the value. This is the copy the question is asking for

visited = {node.val: Node(node.val)}

while queue:

current_node = queue.popleft()

current_clone = visited[current_node.val]

for neighbour in current_node.neighbors:

if neighbour.val not in visited:

# Note: a new Node is created with the neighbour's val. This is the copy mechanism

visited[neighbour.val] = Node(neighbour.val)

queue.append(neighbour)

# Note: The node that is appended is the one from the visited hash. This is the copy value

current_clone.neighbors.append(visited[neighbour.val])

# Note: return from the visited hash, as it holds the copied graph

return visited[node.val]

Last modified 1yr ago