Clone Undirected Graph

Problem

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<Node> neighbors;
}

OR

class UndirectedGraphNode {
	int val;
	List<UndirectedGraphNode> neighbors;
	UndirectedGraphNode(int x) {
		val = x;
		neighbors = new ArrayList<UndirectedGraphNode> ();
	}
};

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.

Examples

Example 1:

graph LR

    subgraph Original
        A1[1]:::orig
        B1[2]:::orig
        C1[3]:::orig
        D1[4]:::orig
        
        A1 --- B1 & D1
        B1 --- C1
        D1 --- C1
    end
    
    subgraph Same["Don't return same graph"]
        A2[1]:::orig
        B2[2]:::orig
        C2[3]:::orig
        D2[4]:::orig
        
        A2 --- B2 & D2
        B2 --- C2
        D2 --- C2
    end

    subgraph Correct["Looks same + new nodes"]
        A3[1]:::corr
        B3[2]:::corr
        C3[3]:::corr
        D3[4]:::corr
        
        A3 --- B3 & D3
        B3 --- C3
        D3 --- C3
    end

    subgraph Messy["Wrong connections"]
        A4[1]:::mess
        B4[3]:::mess
        C4[2]:::mess
        D4[4]:::mess
        
        A4 --- B4 & D4
        B4 --- C4
        D4 --- C4
    end
    
    Original --x Same
    Original --> Correct
    Original --x Messy
    
    classDef orig stroke:#FF8C00,stroke-width:2px
    classDef corr stroke:blue,stroke-width:2px
    classDef mess stroke:#f66,stroke-width:2px

Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2:

graph LR;
   A(1)

Input: adjList = [[]]
Output: [[]]
Explanation: 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.

Example 3:

Input: adjList = []
Output: []
Explanation: This an empty graph, it does not have any nodes.

Solution

A graph clone requires creating a copy of each node and appropriately linking its neighbours in the clone while ensuring each node is cloned only once. So, we can use DFS or BFS to traverse through the graph starting from the given node.

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/UnPCxesy6sE" frameborder="0" allowfullscreen></iframe></div>

Method 1 - DFS

Intuition

The core idea is that to clone a graph, we must create a new node for each original node and ensure all neighbor relationships are preserved. Since graphs may contain cycles, we need to avoid infinite loops and duplicate nodes by keeping track of already-cloned nodes. DFS allows us to traverse the graph deeply, cloning nodes and their neighbors recursively, while a hashmap ensures each node is cloned only once.

Approach

1. If the input node is null, return null.
2. Use a hashmap to map each original node to its clone.
3. For each node, if it has already been cloned (exists in the hashmap), return the clone.
4. Otherwise, create a new node, add it to the hashmap, and recursively clone all its neighbors, adding them to the clone's neighbor list.
5. Return the clone of the starting node.

Approach

1. Mapping
   • Maintain a hashmap (or dictionary) visited that maps each original node to its clone.
   • If a node has already been cloned, use the clone from the hashmap.
   • If not, create a new clone and add it to the hashmap.
2. Build the clone
   • For each node, recursively (or iteratively) visit its neighbours and add the clones' neighbours accordingly.

We can use origToCopyMap containing node and cloned node.

Code

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 {
    // HashMap to store the mapping from original nodes to their cloned counterparts.
    // This helps in avoiding cycles and reusing cloned nodes.
    private HashMap<Node, Node> oldToNewMap = new HashMap<>();

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

        // If the node has already been cloned, return its clone from the map.
        if (oldToNewMap.containsKey(node)) {
            return oldToNewMap.get(node);
        }

        // Create a new node for the current original node.
        Node clonedNode = new Node(node.val, new ArrayList<>());
        // Add the mapping to the HashMap immediately to handle cycles.
        oldToNewMap.put(node, clonedNode);

        // Recursively clone the neighbors and add them to the cloned node's neighbors list.
        for (Node neighbor : node.neighbors) {
            clonedNode.neighbors.add(cloneGraph(neighbor));
        }

        return clonedNode;
    }
}

Python

"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []
"""

from typing import Optional, List

class Solution:
    def __init__(self):
        # HashMap to store the mapping from original nodes to their cloned counterparts.
        # This helps in avoiding cycles and reusing cloned nodes.
        self.old_to_new_map = {}

    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None

        # If the node has already been cloned, return its clone from the map.
        if node in self.old_to_new_map:
            return self.old_to_new_map[node]

        # Create a new node for the current original node.
        cloned_node = Node(node.val)
        # Add the mapping to the HashMap immediately to handle cycles.
        self.old_to_new_map[node] = cloned_node

        # Recursively clone the neighbors and add them to the cloned node's neighbors list.
        for neighbor in node.neighbors:
            cloned_node.neighbors.append(self.cloneGraph(neighbor))
        
        return cloned_node

C++

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> map;
        return dfs(node, map);
    }
    Node* dfs(Node* node, unordered_map<Node*, Node*>& map) {
        if (map.count(node)) return map[node];
        Node* clone = new Node(node->val);
        map[node] = clone;
        for (auto neighbor : node->neighbors) {
            clone->neighbors.push_back(dfs(neighbor, map));
        }
        return clone;
    }
};

Go

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    visited := make(map[*Node]*Node)
    var dfs func(*Node) *Node
    dfs = func(n *Node) *Node {
        if v, ok := visited[n]; ok {
            return v
        }
        clone := &Node{Val: n.Val}
        visited[n] = clone
        for _, neighbor := range n.Neighbors {
            clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
        }
        return clone
    }
    return dfs(node)
}

Kotlin

class Solution {
    fun cloneGraph(node: Node?): Node? {
        if (node == null) return null
        val visited = mutableMapOf<Node, Node>()
        fun dfs(n: Node): Node {
            if (visited.containsKey(n)) return visited[n]!!
            val clone = Node(n.`val`)
            visited[n] = clone
            for (neighbor in n.neighbors) {
                clone.neighbors.add(dfs(neighbor))
            }
            return clone
        }
        return dfs(node)
    }
}

Rust

use std::collections::HashMap;
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn clone_graph(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        fn dfs(
            node: &Option<Rc<RefCell<Node>>>,
            visited: &mut HashMap<i32, Rc<RefCell<Node>>>,
        ) -> Option<Rc<RefCell<Node>>> {
            if let Some(n) = node {
                let val = n.borrow().val;
                if let Some(clone) = visited.get(&val) {
                    return Some(Rc::clone(clone));
                }
                let new_node = Rc::new(RefCell::new(Node {
                    val,
                    neighbors: vec![],
                }));
                visited.insert(val, Rc::clone(&new_node));
                for neighbor in &n.borrow().neighbors {
                    new_node.borrow_mut().neighbors.push(dfs(&Some(Rc::clone(neighbor)), visited).unwrap());
                }
                Some(new_node)
            } else {
                None
            }
        }
        dfs(&node, &mut HashMap::new())
    }
}

Typescript

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;
    const visited = new Map<Node, Node>();
    function dfs(n: Node): Node {
        if (visited.has(n)) return visited.get(n)!;
        const clone = new Node(n.val);
        visited.set(n, clone);
        for (const neighbor of n.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
    return dfs(node);
}

Complexity

• ⏰ Time complexity: O(V + E) where V is the number of vertices (nodes) and E is the number of edges, since we visit each node and edge once.
• 🧺 Space complexity: O(V) for the hashmap and the recursion/queue stack, where V is the number of nodes.

Method 2 - BFS

Intuition

Instead of recursion, we can use BFS to systematically visit each node in the graph layer by layer. By using a queue and a hashmap to track already-cloned nodes, we ensure that each node is cloned exactly once and all neighbor relationships are correctly established. BFS is especially useful for wide graphs and avoids recursion stack overflow.

Approach

1. If the input node is null, return null.
2. Use a hashmap to map each original node to its clone.
3. Initialize a queue and enqueue the starting node, cloning it and adding it to the hashmap.
4. While the queue is not empty:
   • Dequeue a node and iterate through its neighbors.
   • For each neighbor, if it hasn't been cloned, clone it, add it to the hashmap, and enqueue it.
   • Add the neighbor's clone to the current node's clone's neighbor list.
5. Return the clone of the starting node.

We can use BFS by:

• Using a queue, we systematically visit each node layer by layer.
• We create a clone for each node and link its neighbours as we traverse.

Algorithm

1. If the input node is null, return null.
2. Initialise a mapping (visited) that stores the reference to already cloned nodes.
3. Use a queue to traverse the graph.
4. For each node:
   • Clone the node if it hasn’t been cloned already (using visited as a check).
   • Traverse its neighbours, clone them (if necessary), and connect the current node’s clone to its neighbours' clones.
   • Add unvisited neighbours to the queue.
5. Once all nodes are processed, the graph is fully cloned.

Code

Java

// Node is undirected graph
public Node cloneGraph(Node node) {
	if (node == null)
		return null;

	Queue<Node> queue = new LinkedList<Node> ();
	Map<Node, Node> origToCopyMap = new HashMap<Node, Node> ();

	Node newHead = new Node(node.val);

	queue.add(node);
	map.put(node, newHead);

	while (!queue.isEmpty()) {
		Node curr = queue.pop();

		for (Node adjNode: curr.neighbors) {
			if (!origToCopyMap.containsKey(adjNode)) {
				Node copy = new Node(adjNode.val);
				origToCopyMap.put(adjNode, copy);
				origToCopyMap.get(curr).neighbors.add(copy);
				queue.add(adjNode);
			} else {
				origToCopyMap.get(curr)
				.neighbors.add(map.get(adjNode));
			}
		}

	}
	return newHead;
}

Python

from collections import deque
from typing import Optional

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if not node:
            return None
        visited = {}
        queue = deque([node])
        visited[node] = Node(node.val)
        while queue:
            curr = queue.popleft()
            for neighbor in curr.neighbors:
                if neighbor not in visited:
                    visited[neighbor] = Node(neighbor.val)
                    queue.append(neighbor)
                visited[curr].neighbors.append(visited[neighbor])
        return visited[node]

C++

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map<Node*, Node*> map;
        queue<Node*> q;
        q.push(node);
        map[node] = new Node(node->val);
        while (!q.empty()) {
            Node* curr = q.front(); q.pop();
            for (auto neighbor : curr->neighbors) {
                if (!map.count(neighbor)) {
                    map[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                map[curr]->neighbors.push_back(map[neighbor]);
            }
        }
        return map[node];
    }
};

Go

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }
    visited := make(map[*Node]*Node)
    queue := []*Node{node}
    visited[node] = &Node{Val: node.Val}
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        for _, neighbor := range curr.Neighbors {
            if _, ok := visited[neighbor]; !ok {
                visited[neighbor] = &Node{Val: neighbor.Val}
                queue = append(queue, neighbor)
            }
            visited[curr].Neighbors = append(visited[curr].Neighbors, visited[neighbor])
        }
    }
    return visited[node]
}

Kotlin

class Solution {
    fun cloneGraph(node: Node?): Node? {
        if (node == null) return null
        val visited = mutableMapOf<Node, Node>()
        val queue = ArrayDeque<Node>()
        queue.add(node)
        visited[node] = Node(node.`val`)
        while (queue.isNotEmpty()) {
            val curr = queue.removeFirst()
            for (neighbor in curr.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    visited[neighbor] = Node(neighbor.`val`)
                    queue.add(neighbor)
                }
                visited[curr]?.neighbors?.add(visited[neighbor]!!)
            }
        }
        return visited[node]
    }
}

Rust

use std::collections::{HashMap, VecDeque};
use std::rc::Rc;
use std::cell::RefCell;

impl Solution {
    pub fn clone_graph(node: Option<Rc<RefCell<Node>>>) -> Option<Rc<RefCell<Node>>> {
        if node.is_none() {
            return None;
        }
        let node = node.unwrap();
        let mut visited = HashMap::new();
        let mut queue = VecDeque::new();
        queue.push_back(Rc::clone(&node));
        visited.insert(node.borrow().val, Rc::new(RefCell::new(Node {
            val: node.borrow().val,
            neighbors: vec![],
        })));
        while let Some(curr) = queue.pop_front() {
            let curr_val = curr.borrow().val;
            for neighbor in &curr.borrow().neighbors {
                let neighbor_val = neighbor.borrow().val;
                if !visited.contains_key(&neighbor_val) {
                    visited.insert(neighbor_val, Rc::new(RefCell::new(Node {
                        val: neighbor_val,
                        neighbors: vec![],
                    })));
                    queue.push_back(Rc::clone(neighbor));
                }
                visited.get(&curr_val).unwrap().borrow_mut().neighbors.push(
                    visited.get(&neighbor_val).unwrap().clone()
                );
            }
        }
        visited.get(&node.borrow().val).cloned()
    }
}

Typescript

function cloneGraph(node: Node | null): Node | null {
    if (!node) return null;
    const visited = new Map<Node, Node>();
    const queue: Node[] = [node];
    visited.set(node, new Node(node.val));
    while (queue.length > 0) {
        const curr = queue.shift()!;
        for (const neighbor of curr.neighbors) {
            if (!visited.has(neighbor)) {
                visited.set(neighbor, new Node(neighbor.val));
                queue.push(neighbor);
            }
            visited.get(curr)!.neighbors.push(visited.get(neighbor)!);
        }
    }
    return visited.get(node)!;
}

Complexity

• ⏰ Time complexity: O(V+E), because BFS ensures each node and edge is visited once.
• 🧺 Space complexity: O(V) for the hashmap and the BFS queue.