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 {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> map = new HashMap<>();
return dfs(node, map);
}
private Node dfs(Node node, Map<Node, Node> map) {
if (map.containsKey(node)) return map.get(node);
Node clone = new Node(node.val);
map.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(dfs(neighbor, map));
}
return clone;
}
}Follow-up:
How would you optimize the solution for a very large graph?
