Clone Graph
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.
Constraints:
- The number of nodes in the graph is in the range [1, 100].
- 1 <= Node.val <= 100
- Node.random is null or is pointing to some node in the graph.
Examples:
Input: [[2,2],[1,1],[2,0],[0,1,1,2]]
Output: [[2,2],[1,1],[2,0],[0,1,1,2]]
Explanation: The graph is a connected undirected graph with 4 nodes. The node with value 0 has a random pointer to node with value 1 and node with value 2. The node with value 1 has a random pointer to node with value 0 and node with value 2. The node with value 2 has a random pointer to node with value 0 and node with value 1.
Solutions
Depth-First Search (DFS)
The solution uses a depth-first search (DFS) approach to traverse the graph and clone each node. A map is used to keep track of the cloned nodes to avoid cloning the same node multiple times.
class Solution:
def cloneGraph(self, node:
'Node') -> 'Node':
if not node:
return None; map = {};
def dfs(node):
if node in map:
return map[node]; clone = Node(node.val); map[node] = clone; for neighbor in node.neighbors:
clone.neighbors.append(dfs(neighbor)); return clone; return dfs(node)Follow-up:
How would you optimize the solution for a very large graph?
