Skip to content
AI360Xpert
Back to Graphs
Medium

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.

Examples

Input:adjList = [[2,4],[1,3],[2,4],[1,3]]
Output:[[2,4],[1,3],[2,4],[1,3]]
There are 4 nodes in the graph. Node 1's neighbors are Node 2 and Node 4. Node 2's neighbors are Node 1 and Node 3. Node 3's neighbors are Node 2 and Node 4. Node 4's neighbors are Node 1 and Node 3.
Input:adjList = [[]]
Output:[[]]
Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.
Input:adjList = []
Output:[]
This an empty graph, it does not have any nodes.

Constraints

  • The number of nodes in the graph is in the range `[0, 100]`.
  • 1 <= Node.val <= 100
  • Node.val is unique for each node.
  • 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.

Depth-First Search (DFS) with Hash Map

Approach

To avoid getting stuck in cycles, we use a hash map to keep track of nodes we have already copied. The map stores the mapping from the original node to the cloned node. We traverse the graph using DFS. For each visited node, if it is not in the hash map, we clone it and add it to the map. Then, we recursively clone all its neighbors and append them to the cloned node's neighbors list.

Complexity Analysis

Time Complexity
O(V + E)
Space Complexity
O(V)

Time complexity is O(V + E) where V is the number of vertices (nodes) and E is the number of edges, as we process each node and each edge once. Space complexity is O(V) for the hash map and the recursion stack.

Solution.java
/*// 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 to store original node to cloned node mapping        Map<Node, Node> oldToNew = new HashMap<>();        return dfs(node, oldToNew);    }        private Node dfs(Node node, Map<Node, Node> oldToNew) {        // If the node is already cloned, return the cloned instance        if (oldToNew.containsKey(node)) {            return oldToNew.get(node);        }                // Clone the node and add it to the map        Node copy = new Node(node.val);        oldToNew.put(node, copy);                // Clone all neighbors recursively        for (Node neighbor : node.neighbors) {            copy.neighbors.add(dfs(neighbor, oldToNew));        }                return copy;    }}