Leetcode 133. Clone Graph

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.

    
        class Node {
            public int val;
            public List neighbors;
        }
    

Test case format: For simplicity, each node's value is the same as the node's index (1-indexed).

For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph.

Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1.

You must return the copy of the given node as a reference to the cloned graph.

Depth First Search Approach:-

The intuition of this problem is to do copy as we traverse in the graph.

Since, we dealing with graph and a node could have any number of neighbours.

This is why? The neighbours is a list. Now we have a more problem while traversing the graph.

We don't want to get stuck in a cycle while we are traversing the graph.

Now, if you have read the problem's statement, any given undirected edge of graph could be represented as two directional edges.

So if there is an undirected edge between node A and Node B, the graph respresented as two directional edges.

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

class Solution {
    private HashMap vistedNode = new HashMap<>();
    
    public Node cloneGraph(Node node) {
        if(node == null) return node;
        
        if(vistedNode.containsKey(node)) return vistedNode.get(node);
        
        Node cloneNode = new Node(node.val, new ArrayList());
        vistedNode.put(node, cloneNode);
        
        for(Node neighbour : node.neighbors){
            cloneNode.neighbors.add(cloneGraph(neighbour));
        }
        return cloneNode;
    }
}
    

Complexity Analysis

Time Complexity: O(N + M), where N is a number of nodes (vertices) and M is a number of edges.

Space Complexity: O(N)

This space is occupied by the visited hash map and in addition to that, space would also be occupied by the recursion stack since we are adopting a recursive approach here.

The space occupied by the recursion stack would be equal to O(H) where H is the height of the graph. Overall, the space complexity would be O(N).