133. Clone Graph
Problem Description
The problem is about creating a deep copy of a connected undirected graph. A deep copy means a new graph where each node and edge is a replica of the original graph but is an entirely new instance, with no shared references with the original graph.
In a graph, nodes are interconnected through edges. To represent this in code, each node has an integer value and a list of its neighboring nodes. The goal is to copy all the nodes and their connections in such a way that if you manipulate the copied graph, the original graph remains unaffected.
The representation of the graph is done using an adjacency list, which is an array of lists where each list represents a node and contains all of its neighbors. For the purposes of this problem, every node's value is assumed to be unique and equal to its 1-based index in the adjacency list, simplifying the graph's representation and the copying process.
The challenge here is to ensure that while copying the nodes, their neighbors are also copied correctly, and any neighbor connections in the new graph mirror those in the original graph, preserving the structure.
Flowchart Walkthrough
Let's determine the correct traversal algorithm using the Flowchart. Here's a step-by-step analysis for LeetCode 133, Clone Graph:
Is it a graph?
- Yes: The problem involves cloning a graph, so it naturally involves graph data structures.
Is it a tree?
- No: Although the graph may form a tree-like structure, it is not specifically categorized as a tree because it may contain cycles and isn't necessarily hierarchical.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The graph in the Clone Graph problem can have cycles, so it is not acyclic.
Is the problem related to shortest paths?
- No: The challenge is to clone the graph, not to find the shortest path between nodes.
Does the problem involve connectivity?
- Yes, in a sense: We need to traverse through all the nodes to create a clone of the entire graph.
Conclusion: The flowchart and problem requirements suggest using Depth-First Search (DFS) for cloning the graph, as DFS is suited for exhaustive traversal through all nodes, which is essential for replicating each node and edge in the graph.
Intuition
To solve the problem, the idea is to traverse the graph, starting from the given node, and create new nodes as we go. Since the original graph could have cycles or shared neighbors, it is crucial to keep track of the nodes that have already been copied to avoid infinite loops and ensure that neighbors are not duplicated in the new graph.
The algorithm involves a depth-first search (DFS) traversal with the following steps:
-
Initialize a
visited
dictionary that will map original nodes to their corresponding cloned nodes. This will help check if a node has been visited, and also provide a reference to its cloned counterpart. -
Define a recursive function
clone(node)
that takes a node from the original graph.- If the node is
None
, returnNone
(this handles empty graph cases). - If the node has already been visited, return its cloned counterpart from the
visited
dictionary. - If the node is new, create a clone with the same value.
- Store this cloned node in the
visited
dictionary with the original node as the key. - Iteratively clone all the neighbor nodes using the same
clone
function and append them to theneighbors
list of the cloned node.
- If the node is
-
Start the cloning process by calling
clone(node)
on the given node and return its result, which is a reference to the cloned graph's starting node.
By following these steps, we ensure that each node is visited once, and a deep copy of the graph is created, with all the original connections between the nodes preserved in the new graph.
Learn more about Depth-First Search, Breadth-First Search and Graph patterns.
Solution Approach
The solution leverages the depth-first search (DFS) algorithm to iterate through the graph, and a hash map (defaultdict
in Python) to keep track of visited nodes and their clones. This ensures each node is copied exactly once, and we do not run into an infinite loop due to cycles in the graph.
Here's a step-by-step breakdown of the solution approach:
-
Initialization:
- A dictionary
visited
is created to map original nodes to their cloned counterparts. This is essential to:- Track which nodes have already been copied.
- Retrieve the cloned version of a node to set up the
neighbors
references correctly in the cloned graph.
- A dictionary
-
Clone Function:
- The
clone
function is a recursive helper function that performs the DFS. - The function signature
clone(node)
takes a node from the original graph as its argument.
- The
-
Base cases:
- If the input
node
isNone
, meaning either the graph is empty or we've hit the end of a path, the function returnsNone
. - If the input
node
is found in thevisited
dictionary, it means we've already created a clone of this node. We immediately return the cloned node to avoid duplicating nodes or falling into a cycle.
- If the input
-
Cloning Process:
- If the node is being visited for the first time, we create a new
Node
instance with the same value (c = Node(node.val)
). - The new node
c
is then stored invisited[node]
. This step marks the node as copied and provides a reference for its clone.
- If the node is being visited for the first time, we create a new
-
Neighbors Copy:
- We then iterate over the
neighbors
of the current node. For each neighbor, we recursively call theclone
function (clone(e)
) and append the result to thec.neighbors
. - This recursive approach ensures that we explore each neighbor (and subsequently, each neighbor's neighbor, and so on), cloning nodes and stitching together the cloned graph as we traverse the original graph.
- We then iterate over the
-
Returning the Clone:
- Once all neighbors for the node have been processed, the function returns
c
, the clone of the current node, along with all its neighbors properly linked.
- Once all neighbors for the node have been processed, the function returns
-
Invocation:
- The DFS cloning begins with
return clone(node)
, wherenode
is the reference to the node that was provided as input to thecloneGraph
function. - Upon completion, this invocation returns a reference to the newly created deep copy of the graph, which can now be used independently of the original graph.
- The DFS cloning begins with
This solution scales well because the DFS and usage of a hash map ensure that each node is visited and copied exactly once. The complexity of the algorithm is O(N + M), where N is the number of nodes and M is the number of edges in the graph, since every node and edge is visited once in the traversal and copying process.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say we have a small undirected graph represented by the adjacency list [[2,4],[1,3],[2,4],[1,3]]
, which corresponds to the following graph:
1Node 1 -- Node 2 2 | | 3Node 4 -- Node 3
-
Initialization:
- We initialize an empty dictionary called
visited
to keep track of the cloned nodes.
- We initialize an empty dictionary called
-
Start Cloning:
- We begin by calling
clone(node)
on the node with value 1 (Node 1).
- We begin by calling
-
Node 1:
- Since Node 1 isn't in
visited
, we create a cloned nodeC1
and add it tovisited
withvisited[1] = C1
. - We proceed to clone Node 1's neighbors (Node 2 and Node 4).
- Since Node 1 isn't in
-
Node 2:
- We call
clone(node)
on Node 1's first neighbor, Node 2. - Node 2 isn't in
visited
, so we create a cloneC2
and add it tovisited
. - We then clone Node 2's neighbors (Node 1 and Node 3). Since Node 1 is already visited, we link C1 (Node 1's clone) as a neighbor to C2.
- We call
-
Node 3:
- When cloning Node 2's neighbors, we call
clone(node)
on Node 3. - Node 3 isn't in
visited
, so we create a cloneC3
and add it tovisited
. - We clone Node 3's neighbors (Node 2 and Node 4). Node 2's clone, C2, is already in
visited
, so we link C2 as a neighbor to C3.
- When cloning Node 2's neighbors, we call
-
Node 4:
- Now, from Node 1, we clone the second neighbor, Node 4, by calling
clone(node)
on it. - We create
C4
since Node 4 isn't invisited
and add it tovisited
. - We clone Node 4's neighbors (Node 1 and Node 3). Clones for both these nodes (C1 and C3) are found in
visited
, so we link both as neighbors to C4.
- Now, from Node 1, we clone the second neighbor, Node 4, by calling
-
Completing the Graph:
- With all nodes visited, the DFS cloning is complete. Each node in the graph is cloned exactly once, and their neighbors are interconnected following their original structure.
-
Return:
- We return
C1
, which now hasC2
andC4
as its neighbors, representing the start of the cloned graph.
- We return
The cloned graph is now a deep copy of the original and can be manipulated without affecting the original graph. The connections are:
1C1 -- C2 2 | | 3C4 -- C3
Each Ci
denotes the cloned node corresponding to the original node of the same index. The deep copy process ensures that even if the initial graph had a more complex structure with cycles, the algorithm would have correctly cloned it without entering an infinite loop, since each node is visited only once.
Solution Implementation
1from collections import defaultdict
2
3class Node:
4 """
5 # Definition for a Node in the graph.
6 """
7 def __init__(self, val=0, neighbors=None):
8 self.val = val
9 self.neighbors = neighbors if neighbors is not None else []
10
11
12class Solution:
13 def cloneGraph(self, node: 'Node') -> 'Node':
14 # Dictionary to keep track of visited nodes and their clones.
15 visited = defaultdict(Node)
16
17 def clone(node: 'Node') -> 'Node':
18 """
19 clone is a helper function which performs a depth-first traversal
20 of the graph to create a deep copy of it.
21
22 :param node: The graph node to be cloned
23 :return: The cloned copy of the input node
24 """
25 # Return None for a non-existent node
26 if node is None:
27 return None
28
29 # If the node has already been visited, return the cloned node
30 if node in visited:
31 return visited[node]
32
33 # Create a new Node clone with the value of the original node
34 clone_node = Node(node.val)
35
36 # Map the original node to the cloned one in visited dictionary
37 visited[node] = clone_node
38
39 # For every adjacent node, create a clone copy to the neighbors of the cloned node
40 for neighbor in node.neighbors:
41 clone_node.neighbors.append(clone(neighbor))
42
43 return clone_node
44
45 # Start the graph cloning process from the input node
46 return clone(node)
47
1import java.util.HashMap;
2import java.util.List;
3import java.util.Map;
4
5// Definition for a graph node.
6class Node {
7 public int val;
8 public List<Node> neighbors;
9
10 public Node() {
11 val = 0;
12 neighbors = new ArrayList<>();
13 }
14
15 public Node(int _val) {
16 val = _val;
17 neighbors = new ArrayList<>();
18 }
19
20 public Node(int _val, ArrayList<Node> _neighbors) {
21 val = _val;
22 neighbors = _neighbors;
23 }
24}
25
26class Solution {
27
28 // A HashMap to keep track of all the nodes which have already been copied.
29 private Map<Node, Node> visited = new HashMap<>();
30
31 // This function returns the clone of the graph.
32 public Node cloneGraph(Node node) {
33 // If the input node is null, then return null.
34 if (node == null) {
35 return null;
36 }
37
38 // If the node has already been visited i.e., already cloned,
39 // return the cloned node from the map.
40 if (visited.containsKey(node)) {
41 return visited.get(node);
42 }
43
44 // Create a new node with the value of the input node (clone it).
45 Node cloneNode = new Node(node.val);
46 // Mark this node as visited by putting into the visited map.
47 visited.put(node, cloneNode);
48
49 // Iterate over all the neighbors of the input node.
50 for (Node neighbor : node.neighbors) {
51 // Perform a depth-first search (DFS) for each neighbor,
52 // and add the clone of the neighbor to the neighbors list
53 // of the clone node.
54 cloneNode.neighbors.add(cloneGraph(neighbor));
55 }
56
57 // Return the cloned graph node.
58 return cloneNode;
59 }
60}
61
1#include <unordered_map>
2#include <vector>
3
4// Forward declaration of the Node class to use it in the Solution.
5class Node {
6public:
7 int val;
8 std::vector<Node*> neighbors;
9 Node() : val(0) {}
10 Node(int _val) : val(_val) {}
11 Node(int _val, std::vector<Node*> _neighbors) : val(_val), neighbors(_neighbors) {}
12};
13
14class Solution {
15public:
16 // A dictionary to keep track of all visited nodes and their clones.
17 std::unordered_map<Node*, Node*> visited;
18
19 // Function to clone a graph.
20 Node* cloneGraph(Node* node) {
21 // If the input node is null, return null indicating no node to clone.
22 if (!node) return nullptr;
23
24 // If the node has been already visited, return the clone from visited.
25 if (visited.find(node) != visited.end()) return visited[node];
26
27 // Create a new node with the same value as the input node.
28 Node* cloneNode = new Node(node->val);
29 // Record the visited node by mapping the original node to the clone.
30 visited[node] = cloneNode;
31
32 // Iterate over all neighbors of the input node.
33 for (auto& neighbor : node->neighbors) {
34 // Recursively call cloneGraph for each neighbor and add it to the cloned node's neighbors.
35 cloneNode->neighbors.push_back(cloneGraph(neighbor));
36 }
37
38 // Return the cloned node.
39 return cloneNode;
40 }
41};
42
1// Function to clone a graph. Returns a cloned copy of the given graph node or null if the input node is null.
2function cloneGraph(originalNode: Node | null): Node | null {
3 // If the original node is null, return null as there is nothing to clone.
4 if (originalNode === null) return null;
5
6 // Map to hold visited nodes to avoid duplication and for constant-time look-up.
7 const visitedMap = new Map<Node, Node>();
8
9 // Clone the original node and store the mapping.
10 visitedMap.set(originalNode, new Node(originalNode.val));
11
12 // Queue for BFS traversal starting at the original node.
13 const queue: Node[] = [originalNode];
14
15 // Traverse the graph in a breadth-first manner
16 while (queue.length > 0) {
17 // Remove the first node from the queue to process its neighbors.
18 const currentNode = queue.shift();
19
20 // Process all the neighbors of the current node.
21 for (let neighbor of currentNode.neighbors) {
22 // If this neighbor hasn't been visited/processed yet.
23 if (!visitedMap.has(neighbor)) {
24 // Clone the neighbor and put it in the map.
25 queue.push(neighbor);
26 visitedMap.set(neighbor, new Node(neighbor.val));
27 }
28 // Add the cloned neighbor to the neighbors list of the cloned current node.
29 const clonedCurrentNode = visitedMap.get(currentNode);
30 clonedCurrentNode.neighbors.push(visitedMap.get(neighbor));
31 }
32 }
33 // Return the cloned node that corresponds to the original input node.
34 return visitedMap.get(originalNode);
35}
36
Time and Space Complexity
Time Complexity
The time complexity of the cloneGraph
function is O(N + M)
, where N
is the number of nodes in the graph and M
is the number of edges. This is because each node is visited exactly once during the clone operation. When visiting each node, all of its neighbors are iterated through to copy their references, contributing to the M
term in the complexity.
Space Complexity
The space complexity of the cloneGraph
function is also O(N)
, where N
is the number of nodes in the graph. This space is used to store cloned nodes in the visited
dictionary to keep track of already cloned nodes, ensuring nodes are not cloned multiple times. The space complexity also includes the recursion stack, which in case of a deep graph could be O(N)
in the worst case (when the graph is a linked list). However, in the average case of a typical graph, the recursion stack will not grow linearly with the number of nodes and will be smaller.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.