Design Gurus Logo
Blind 75
Solution: Clone Graph

Problem Statement

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 (List[Node]) of its neighbors.

Example 1:

Input:

    1--2
    |  |
    4--3

Expected Output:

    1--2
    |  |
    4--3

Explanation: The graph has four nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to nodes 1 and 3.

Example 2:

Input:

    1--2
   /    \
  5      3
         |
         4

Expected Output:

    1--2
   /    \
  5      3
         |
         4

Explanation: The graph consists of five nodes with these connections:

  • Node 1 is connected to nodes 2 and 5.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 4.
  • Node 4 is connected to node 3.
  • Node 5 is connected to node 1.

Example 3:

Input:

    1--2
   /    \
  4      3
   \    /
    5--6

Expected Output:

    1--2
   /    \
  4      3
   \    /
    5--6

Explanation: The graph has six nodes with the following connections:

  • Node 1 is connected to nodes 2 and 4.
  • Node 2 is connected to nodes 1 and 3.
  • Node 3 is connected to nodes 2 and 6.
  • Node 4 is connected to nodes 1 and 5.
  • Node 5 is connected to nodes 4 and 6.
  • Node 6 is connected to nodes 3 and 5.

Constraints:

  • The number of nodes in the graph is in the range [0, 100].
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • There are no repeated edges and no self-loops in the graph.
  • The Graph is connected and all nodes can be visited starting from the given node.

Solution

To deep clone a given graph, the primary approach is to traverse the graph using Depth-First Search (DFS) and simultaneously create clones of the visited nodes. A hashmap (or dictionary) is utilized to track and associate original nodes with their respective clones, ensuring no duplications.

  1. Initialization: Create an empty hashmap to match the original nodes to their clones.

  2. DFS Traversal and Cloning: Traverse the graph with DFS. When encountering a node not in the hashmap, create its clone and map them in the hashmap. Recursively apply DFS for each of the node's neighbors. After cloning a node and all its neighbors, associate the cloned node with the clones of its neighbors.

  3. Termination: Once DFS covers all nodes, return the cloned version of the starting node.

Algorithm Walkthrough (using Example 1):

For the input graph:

    1--2
    |  |
    4--3
  • Start with an empty hashmap visited.
  • Begin DFS with node 1.
    • Node 1 isn't in visited. Clone it to get 1' and map (1, 1') in the hashmap.
    • For each neighbor of node 1, apply DFS.
      • First with 2.
        • Node 2 isn't in visited. Clone to get 2' and map (2, 2').
        • Node 2's neighbors are 1 and 3. Node 1 is visited, so link 2' to 1'. Move to 3.
          • Node 3 isn't in visited. Clone to get 3' and map (3, 3').
          • Node 3 has neighbors 2 and 4. Node 2 is visited, so link 3' to 2'. Move to 4.
            • Node 4 isn't in visited. Clone to get 4' and map (4, 4').
            • Node 4 has neighbors 1 and 3, both visited. Link 4' to 1' and 3'.
  • With DFS complete, return the clone of the starting node, 1'.

Code

Python3
Python3

Complexity Analysis

  • Time Complexity: O(N+M) where N is the number of nodes and M is the number of edges. Each node and edge is visited once.

  • Space Complexity: O(N) as we are creating a clone for each node. Additionally, the recursion stack might use O(H) where H is the depth of the graph (in the worst case this would be O(N).