Java: Clone Graph

Thought Process

To clone a graph, we need to create a deep copy of all its nodes and their connections. We use a Breadth-First Search (BFS) approach to traverse the original graph. Also, we maintain a hash map to store the mapping between the original nodes and their corresponding cloned nodes. This ensures that we do not create duplicate copies of the same node.

We start by cloning the root node and adding it to the queue. For each node, we iterate through its neighbors. If a neighbor hasn't been cloned yet, we create a new clone and add it to the hash map and the queue. Further, we add the cloned neighbor to the adjacency list of the current cloned node. This process continues until the queue is empty. 

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

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

        Map<Node,Node> mp = new HashMap<>();
        Queue<Node> qu = new LinkedList<>();

        mp.put(node,new Node(node.val));
        qu.offer(node);

        while(!qu.isEmpty()){

            Node nod = qu.poll();
            // Iterate Neighbor element of nod
            for(Node padosi : nod.neighbors){

                // if neighbor elements doesn't exist in map
                if(!mp.containsKey(padosi)){
                    mp.put(padosi,new Node(padosi.val));
                    qu.offer(padosi);
                }
                // Add the neighbor in our cloned graph.
                mp.get(nod).neighbors.add(mp.get(padosi));
            }
        }
        return mp.get(node);
    }
}

Code Complexity

Time Complexity: O(V + E)

The algorithm traverses each node (V) and each edge ( E) exactly once, making it linear in terms of the number of nodes and edges.

Space Complexity: O(V)

The algorithm uses a hash map to store all the nodes, which requires space proportional to the number of nodes (V).

Code copied!