Clone Graph medium

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 (val) and a list (neighbors) of its neighbors.

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]

Output: [[2,4],[1,3],[2,4],[1,3]]

Explanation: There are 4 nodes in the graph. Node 1 has 2 neighbours 2 and 4. Node 2 has 2 neighbours 1 and 3. Node 3 has 2 neighbours 2 and 4. Node 4 has 2 neighbours 1 and 3. The graph is completely connected.

Example 2

Input: adjList = [[]]

Output: [[]]

Explanation: There is only 1 node in the graph and this node does not have any neighbours.

Steps

1. Create a HashMap to store visited nodes: We'll use a HashMap to keep track of nodes we've already cloned. The key will be the original node, and the value will be its cloned counterpart. This prevents infinite recursion in cyclic graphs.

2. Recursive Depth-First Search (DFS): We'll use a recursive DFS function to traverse the graph.

3. Clone the node: For each node encountered, we'll create a new node with the same value.

4. Clone the neighbors: For each neighbor of the current node, we'll recursively call the DFS function to clone the neighbor. If the neighbor has already been cloned (exists in the HashMap), we'll use the cloned version. Otherwise, we'll clone it and add it to the HashMap.

5. Connect the cloned neighbors: Add the cloned neighbors to the neighbors list of the cloned current node.

Explanation

The key to solving this problem efficiently is using a HashMap to avoid redundant cloning and handle cycles. Without the HashMap, you'd end up in infinite recursion if the graph contains cycles. The DFS approach ensures that we explore the entire graph systematically, cloning each node and its connections only once.

Code

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}
    public Node(int _val) { val = _val; }
    public Node(int _val, List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

class Solution {
    Map<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        Node cloneNode = new Node(node.val);
        visited.put(node, cloneNode);
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}

Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. We visit each node and each edge once.
• Space Complexity: O(V), primarily due to the visited HashMap which stores at most V nodes. The recursive call stack could also contribute to space complexity in the worst case (deep graph), but it is still bounded by V.

This solution provides a clear, concise, and efficient approach to cloning a graph, handling both simple and complex graph structures including those with cycles. Remember to handle the base case of node == null to prevent NullPointerExceptions.