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.
function cloneGraph(node) {
if (!node) return null;
const map = new Map();
function dfs(node) {
if (map.has(node)) return map.get(node);
const clone = new Node(node.val);
map.set(node, clone);
for (const neighbor of node.neighbors) {
clone.neighbors.push(dfs(neighbor));
}
return clone;
}
return dfs(node);
}
Follow-up:
How would you optimize the solution for a very large graph?
