Given a reference to a node in a connected undirected graph, return a
deep copy (clone) of the graph.
Each node contains a value and a list of its neighbors.
Input: adjList = [[2,4],[1,3],[2,4],[1,3]]
Output: [[2,4],[1,3],[2,4],[1,3]]
Explanation: 4-node graph where 1—2—3—4—1 form a cycle.
Node definition:
class Node {
public int val;
public List<Node> neighbors;
public Node(int val) { this.val = val; this.neighbors = new ArrayList<>(); }
}
Contents
- Solution 1 — BFS
- Solution 2 — DFS
- Complexity Analysis
BFS
Use a HashMap<Node, Node> mapping original nodes to their clones.
BFS from the start node; for each node, clone it and wire up its neighbors.
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> cloneMap = new HashMap<>();
Queue<Node> queue = new LinkedList<>();
cloneMap.put(node, new Node(node.val));
queue.offer(node);
while (!queue.isEmpty()) {
Node curr = queue.poll();
for (Node neighbor : curr.neighbors) {
if (!cloneMap.containsKey(neighbor)) {
cloneMap.put(neighbor, new Node(neighbor.val));
queue.offer(neighbor);
}
// Wire the cloned neighbor to the cloned current node
cloneMap.get(curr).neighbors.add(cloneMap.get(neighbor));
}
}
return cloneMap.get(node);
}
DFS
private Map<Node, Node> cloneMap = new HashMap<>();
public Node cloneGraph(Node node) {
if (node == null) return null;
if (cloneMap.containsKey(node)) return cloneMap.get(node); // already cloned
Node clone = new Node(node.val);
cloneMap.put(node, clone);
for (Node neighbor : node.neighbors) {
clone.neighbors.add(cloneGraph(neighbor)); // recursively clone neighbors
}
return clone;
}
- Time: O(V + E) — every node and edge is visited once.
- Space: O(V) — HashMap holds one clone per node.