Backtracking Algorithm In Graphs Question: Clone Graph

Given a graph clone a graph make deep copy of it

graph TD;
	1-->2;
	1-->4;
	2-->1;
	2-->3;
	3-->2;
	3-->4;
	4-->1;
	4-->3;

Simple : we need to create a map which will have original node and new created node as a reference to it. Then since the node class has a value and node reference attached to it, we need to add the neighbours to it as we clone the new node Below code shows how we can clone a graph based on a given Node

Deep copy of the graph to be returned, ordering of the graph should not be changed

       Map<Node,Node> clone = new HashMap<>();
       public Node backtrackCloneGraphDFS(Node node) {
           if(node==null) return null;              //if the node's empty return null, else:

        	Node newClonedNode = new Node(node.val);         //creating a copy of original node and assigining its value to copy
        	clone.put(node,newClonedNode);                   //adding the element into the map w/ node and copy of that node as key value pair
        	for(Node neighbor : node.neighbors){    //now, traversing the neighbors of the node
           		if(!clone.containsKey(neighbor)) {  //if the neig is not in hashmap, we create it
              		newClonedNode.neighbors.add(backtrackCloneGraphDFS(neighbor)); //calling the function again to add the neighbor of the 
                                                    //cloned node, we can't do add(node.neighbor) cause that
                                                    //will be a reference to original graph
           	} else{                                 //neighbor is already present in hashmap, we simply add it to our clone
           		newClonedNode.neighbors.add(clone.get(neighbor)); //No neighbours
           	}
        }
        return newClonedNode;
    }