medium 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

import java.util.*;

//    public static class GraphNode {
//         public int val;
//         public List<GraphNode> neighbors;

//         public GraphNode() {
//             val = 0;
//             neighbors = new ArrayList<GraphNode>();
//         }

//         public GraphNode(int _val) {
//             val = _val;
//             neighbors = new ArrayList<GraphNode>();
//         }

//         public GraphNode(int _val, ArrayList<GraphNode> _neighbors) {
//             val = _val;
//             neighbors = _neighbors;
//         }
//     }

class Solution {

  // HashMap to store already visited nodes and their clones
  private Map<GraphNode, GraphNode> visited = new HashMap<>();

  public GraphNode cloneGraph(GraphNode node) {
    // Base condition if node is null
    if (node == null) return null;

    // Return the clone from the map if it's already visited
    if (visited.containsKey(node)) return visited.get(node);

    // Create a new node for the given value
    GraphNode cloneNode = new GraphNode(node.val, new ArrayList<>());
    visited.put(node, cloneNode);

    // Process all the neighbors for the node
    for (GraphNode neighbor : node.neighbors) {
      cloneNode.neighbors.add(cloneGraph(neighbor));
    }

    return cloneNode;
  }

  // Utility function to print the structure of the graph
  public static void printGraph(GraphNode node) {
    Set<GraphNode> printed = new HashSet<>();
    Queue<GraphNode> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
      GraphNode curr = queue.poll();
      if (!printed.contains(curr)) {
        System.out.print(curr.val + "-->");
        for (GraphNode n : curr.neighbors) {
          queue.add(n);
          System.out.print(n.val + " ");
        }
        System.out.println();
        printed.add(curr);
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();

    // Example 1: Create a simple two-node graph and clone it
    GraphNode node1 = new GraphNode(1);
    GraphNode node2 = new GraphNode(2);
    node1.neighbors = Arrays.asList(node2);
    node2.neighbors = Arrays.asList(node1);
    printGraph(sol.cloneGraph(node1)); // Expecting: 1-->2, 2-->1
  }
}

Complexity Analysis

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

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