Clone Graph

Problem Statement

LeetCode-133: 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 and a list of its neighbors.

• 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.
• For simplicity, each node’s value is the same as the node’s index (1-indexed).

Approach

We can use both DFS and BFS to solve this problem. Let us first visit the nodes using DFS.

1. Initialize a HashMap to store the mapping of the original node to the cloned node. This will help us avoid visiting the same node multiple times.
2. Start by visiting the given node and create a new node with the same value.
3. Add the mapping of the original node to the cloned node in the HashMap.
4. Visit all the neighbors of the original node and recursively create the cloned nodes for them.
5. Add the cloned neighbors to the cloned node.
6. Return the cloned node.

Similarly, we can solve the problem using BFS.

1. Like DFS, initialize a HashMap to store the mapping of the original node to the cloned node. Also, initialize a Queue to store the nodes that need to be visited.
2. Populate the queue with the given node. Additionally, create a clone of the given node and add it to the HashMap.
3. While the queue is not empty, pop the node from the queue. For each of its neighbor:
   1. If the neighbor is already visited, get the cloned node from the HashMap.
   2. Else, create a new node with the same value and add it to the queue, and the HashMap.
   3. Finally, add the cloned neighbor to the cloned node.
4. Return the cloned node.

Implementation

Here is a Java implementation of the above approach using DFS.

private final Map<Node, Node> cache = new HashMap<>();

public Node cloneGraph(Node node) {
    if(null == node){
        return node;
    }
    
    // reuse the cloned node if already created
    if(cache.containsKey(node)){
        return cache.get(node);
    }

    // clone the node and add to the cache
    Node clone = new Node(node.val);
    cache.put(node, clone);
    
    // clone the neighbors
    for(Node neighbor : node.neighbors){
        Node clonedNeighbor = cloneGraph(neighbor);
        clone.neighbors.add(clonedNeighbor);
    }
    
    return clone;
}

Let us now implement the above approach using BFS.

public Node cloneGraph(Node node) {
    if (null == node) {
        return node;
    }

    Map<Node, Node> cache = new HashMap<>();
    cache.put(node, new Node(node.val));
    
    Queue<Node> queue = new LinkedList<>();
    queue.add(node);

    while (!queue.isEmpty()) {
        Node root = queue.remove();
        for (Node neighbor : root.neighbors) {
            Node clonedNeighbor = null;

            if (cache.containsKey(neighbor)) {
                clonedNeighbor = cache.get(neighbor);
            } else {
                clonedNeighbor = new Node(neighbor.val);
                queue.add(neighbor);
                cache.put(neighbor, clonedNeighbor);
            }

            cache.get(root).neighbors.add(clonedNeighbor);
        }
    }
    return cache.get(node);
}

Complexity Analysis

The time complexity for both DFS and BFS is $O(N + E)$, where $N$ is the number of nodes and $E$ is the number of edges in the graph.

For DFS, the space complexity is $O(N + H) \approx O(N)$ due to the recursion Stack and the HashMap. Here, H is the height of the graph. Similarly, for BFS, the space complexity is $O(N + E) \approx O(N)$ due to the Queue and the HashMap.