Clone Graph

Share

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.

Example
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:
Java
class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int val) { this.val = val; this.neighbors = new ArrayList<>(); }
}

Contents

Solution 1: 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.

Java
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);
}

Solution 2: DFS
Java
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;
}

Complexity Analysis