133. Clone Graph

Description

See: https://leetcode.com/problems/clone-graph/

Given a graph, return a deep copy of it.

Solution

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]