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;
}
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.
For example:
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.
Another example:
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.
How would you implement a deep copy of a graph given a starting node? Consider edge cases such as empty graphs or graphs with a single node. Discuss the time and space complexity of your solution.
Given a reference to a node in a connected undirected graph, the goal is to create a deep copy (clone) of the graph. Each node in the graph contains a value (integer) and a list of its neighbors. The graph is represented using an adjacency list where each list describes the set of neighbors of a node in the graph. The value of each node is the same as its index (1-indexed). The given node will always be the first node with val = 1
. The function should return the copy of the given node as a reference to the cloned graph.
The brute force approach would involve traversing the original graph and creating new nodes with the same values. A simple way to accomplish this is using Depth-First Search (DFS) or Breadth-First Search (BFS). As we visit each node in the original graph, we create a corresponding node in the cloned graph.
The optimal solution also involves using DFS or BFS, but with a mechanism to avoid infinite loops and to efficiently create the cloned graph. A hash map (or dictionary) is typically used to store the mapping between the nodes in the original graph and their corresponding nodes in the cloned graph. This ensures that each node is cloned only once, and that neighbors are correctly linked.
Algorithm:
Code (Python):
class Node:
def __init__(self, val, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
def cloneGraph(node: 'Node') -> 'Node':
if not node:
return None
old_to_new = {}
def clone(node):
if node in old_to_new:
return old_to_new[node]
copy = Node(node.val)
old_to_new[node] = copy
for neighbor in node.neighbors:
copy.neighbors.append(clone(neighbor))
return copy
return clone(node)
The run-time complexity is O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit each node and each edge once.
The space complexity is O(V), where V is the number of vertices (nodes) in the graph. This is because, in the worst case, we may need to store all nodes in the hash map.