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 thecurrent_nodeneighbors 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 thecurrent_cloneneighbors 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 9mo ago