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:
[0, 100]
.1 <= Node.val <= 100
Node.val
is unique for each node.This problem requires creating a deep copy of a graph, ensuring that all nodes and edges are duplicated. The graph is represented using a Node class with a value and a list of neighboring nodes. We'll explore Depth-First Search (DFS) and Breadth-First Search (BFS) approaches.
This approach uses recursion and a hash map (dictionary in Python) to track visited nodes. The clone
function recursively explores the graph:
null
, it returns null
.visited
map, it returns the cloned version from the map, avoiding cycles.visited
map.Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. Each node and edge is visited once.
Space Complexity: O(V) for the visited
map, storing at most all the nodes in the worst-case scenario (a fully connected graph). The recursive call stack also adds space complexity, but this is at most proportional to the height of the graph, which in the worst case is equal to V.
This approach uses a queue for iterative traversal, also utilizing a hash map to track visited nodes.
visited
map is created and the root node is cloned and added to both the visited
map and a queue.visited
, clone it, add it to visited
and the queue.Time Complexity: O(V + E), same as DFS. Each node and edge is visited once.
Space Complexity: O(V), for both the visited
map and the queue, which may store all the nodes in the worst case.
The code examples provided in the prompt demonstrate both DFS and BFS implementations in multiple languages. The DFS solution is generally more concise, while the BFS solution might be slightly easier to understand for those less familiar with recursion. Choose the implementation that best suits your understanding and preferred language. Both have the same time and space complexity.
Remember that the Node class definition needs to be included in each language's implementation. The specific details might vary depending on the language's syntax, but the core logic remains the same.