We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Clone Graph

Difficulty: Medium

Problem Description

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list of its neighbors.

Key Insights

  • The graph is represented using an adjacency list.
  • Each node is guaranteed to have a unique value.
  • The graph is connected, meaning all nodes can be reached from the given node.
  • A deep copy involves creating new instances of nodes while retaining the structure of the graph.

Space and Time Complexity

Time Complexity: O(V + E) where V is the number of nodes and E is the number of edges.
Space Complexity: O(V) for storing the cloned nodes and their relationships.

Solution

To solve the problem, we can use either Depth-First Search (DFS) or Breadth-First Search (BFS) for traversing the graph. We will maintain a mapping from the original nodes to their corresponding cloned nodes to handle the neighbors properly.

  1. Use a dictionary (hash table) to keep track of cloned nodes.
  2. Start from the given node, clone it, and recursively or iteratively clone its neighbors.
  3. For each neighbor, check if it has already been cloned. If not, clone it and continue the process.

Code Solutions

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':
    if not node:
        return None
    
    # A mapping from original nodes to their clones
    node_map = {}
    
    def dfs(current_node):
        if current_node in node_map:
            return node_map[current_node]
        
        # Clone the node
        clone_node = Node(current_node.val)
        node_map[current_node] = clone_node
        
        # Clone neighbors
        for neighbor in current_node.neighbors:
            clone_node.neighbors.append(dfs(neighbor))
        
        return clone_node
    
    return dfs(node)
← Back to All Questions