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.

1
2
3
4


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

1
2
3
4
5
6
7
8


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

1
2
3
4
5
6
7


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)

1
2
3


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:

1
2
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.

Method 1 - DFS

Approach

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.
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


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

        // Map to store clones of nodes
        Map<Node, Node> visited = new HashMap<>();

        // DFS function
        return dfs(node, visited);
    }

    private Node dfs(Node node, Map<Node, Node> visited) {
        // If the node is already cloned, return its clone
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Clone the node
        Node clone = new Node(node.val);
        visited.put(node, clone);

        // Recursively clone neighbours
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(dfs(neighbor, visited));
        }

        return clone;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


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

        # Map to store clones of nodes
        visited: dict[Node, Node] = {}

        # DFS function
        def dfs(nd: Node) -> Node:
            # If the node is already cloned, return its clone
            if nd in visited:
                return visited[nd]

            # Clone the node
            clone = Node(nd.val)
            visited[nd] = clone

            # Recursively clone neighbours
            for nbr in nd.neighbors:
                clone.neighbors.append(dfs(nbr))

            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

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

If the input node is null, return null.
Initialise a mapping (visited) that stores the reference to already cloned nodes.
Use a queue to traverse the graph.
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.
Once all nodes are processed, the graph is fully cloned.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


// 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;
}

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.

Problem#

Examples#

Solution#

Method 1 - DFS#

Approach#

Code#

Complexity#

Method 2 - BFS#

Algorithm#

Complexity#

Problem

Examples

Solution

Method 1 - DFS

Approach

Code

Complexity

Method 2 - BFS

Algorithm

Complexity