Clone Graph

The idea of the algorithm is to make a deepcopy of a graph. Here is a list of the important step of the algorithm:

• Copying a node value is done by creating a new instance of Node with the original node value as val
• Then the code iterates over the neighbors of the original node and create copy that are added as neighbors
• Every original node that has already been copied must be stored to be sure to not copy twice the same node
• The already copied original nodes that are stored should also point to their copy (in a dictionnary structure)
• A queue is used to store the node that remains to process

from collections import deque

"""
# 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 []
"""

def cloneGraph(node: 'Node') -> 'Node':
    # Check if node exist otherwise None value will be add in queue and we'll check for argument on a None value
    if not node:
        return(node)

    # Use a dict to store the nodes (needed for the output)
    set_node, dict_clone, queue = set(), dict(), deque([node])

    while queue:
        curr_node = queue.popleft()

        # set_node is the set of already processed nodes; hence check if already processed
        if curr_node not in set_node:
            set_node.add(curr_node)

            # Add curr_node to dict_clone if not already in
            if curr_node not in dict_clone:
                dict_clone[curr_node] = Node(curr_node.val)

            # Add every child of curr_node in dict if not already and add them as neigbors of the current clone node. Add them also in the queue to process them later
            for child_node in curr_node.neighbors:
                if child_node not in dict_clone:
                    dict_clone[child_node] = Node(child_node.val)
                dict_clone[curr_node].neighbors.append(dict_clone[child_node])
                queue.append(child_node)


    return(dict_clone[node])