Clone Graph
Problem Description
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;}
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.
Example 1:
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:
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.
Constraints:
- The number of nodes in the graph is in the range
[0, 100]. 1 <= Node.val <= 100Node.valis 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.
Solve it on LeetCode
Approaches
1. Depth-First Search (DFS)
Intuition:
The DFS approach involves recursively creating clone nodes and copying the connections (neighbors) in a depth-first manner. We use a hashmap to store the node's original as a key and its clone as a value to avoid creating multiple copies of the same node.
Steps:
- A base case checks if the input node is
null, returningnullif true. - If the node has already been cloned (exists in the hashmap), return the cloned node.
- Initiate a clone node and store it in the hashmap.
- Recursively visit each neighbor of the node and add the cloned neighbors to the clone node's neighbors list.
- Return the cloned node.
Code:
- Time Complexity: O(N), where N is the number of nodes. Each node and edge is traversed once.
- Space Complexity: O(N) due to the recursion stack and hashmap storage of the nodes.
2. Breadth-First Search (BFS)
Intuition:
This approach consists of a breadth-first traversal using a queue. It uses a hashmap to store cloned nodes and iteratively connects neighbors by dequeuing nodes and exploring their neighbors.
Steps:
- Handle the base case where input node is
nullby returningnull. - Use a hashmap to store visited and cloned nodes.
- Initialize a queue with the original node and clone the root node.
- While the queue is not empty, process the node:
- For each neighbor, if not cloned, clone and enqueue it.
- Update the current node's clone to include the clone of its neighbors.
- Once traversal ends, return the clone of the original node.
Code:
- Time Complexity: O(N), where N is the number of nodes. Each node and edge is traversed once.
- Space Complexity: O(N) for the hashmap and queue.