LC 0133 [M] Clone Graph - ALawliet/algorithms GitHub Wiki

use a hashmap of node to its clone which also keeps track of the visited nodes and just BFS

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return node
        
        Q = deque([node])
        
        node_to_clone = {node: Node(node.val, [])} # also acts as visited set
        
        while Q:
            u = Q.popleft()
            
            for v in u.neighbors:
                if v not in node_to_clone: # only clone and queue if it is not already visited
                    node_to_clone[v] = Node(v.val, [])
                    Q.append(v)
                    
                node_to_clone[u].neighbors.append(node_to_clone[v]) # needs to go out here so it always happens
                
        return node_to_clone[node]
"""
# 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 not node: return node

        # Dictionary to save the visited node and it's respective clone
        # as key and value respectively. This helps to avoid cycles.
        visited_to_clone = {} # visited node => clone

        # Put the first node in the queue
        Q = deque([node])
        # Clone the node and put it in the visited dictionary.
        visited_to_clone[node] = Node(node.val, [])

        # Start BFS traversal
        while Q:
            # Pop a node say "n" from the from the front of the queue.
            parent = Q.popleft()

            # Iterate through all the neighbors of the node
            for child in parent.neighbors:
                if child not in visited_to_clone:
                    # Clone the neighbor and put in the visited, if not present already
                    visited_to_clone[child] = Node(child.val, [])
                    # Add the newly encountered node to the queue.
                    Q.append(child)

                # Add the clone of the neighbor to the neighbors of the clone node "n".
                visited_to_clone[parent].neighbors.append(visited_to_clone[child]) # copy neighbors

        # Return the clone of the node from visited.
        return visited_to_clone[node]