6.1 Clone Graph

6.1.1 Problem Metadata

6.1.2 Description

Deep-copy an undirected graph represented as adjacency lists where each node holds a val and a list of neighbors. Input is a reference to a node in the original graph; output should be a structurally identical graph with all new nodes.

6.1.3 Examples

Example 1: Simple Connected Graph

Input: adjacencyList = [[2,4],[1,3],[2,4],[1,3]]
(Node 1 → neighbors [2,4], Node 2 → neighbors [1,3], Node 3 → neighbors [2,4], Node 4 → neighbors [1,3])
Output: A clone graph with the same structure and values but different node objects

Example 2: Single Node

Input: adjacencyList = [[]]
Output: A clone of the single node with empty neighbor list

Example 3: Disconnected Component

Input: adjacencyList = [[2],[1]]
Output: A clone graph with just nodes 1 and 2 connected to each other

6.1.4 Constraints

  • 1 ≤ Node.val ≤ 100
  • Graph nodes are numbered 1 to 100
  • Graph is undirected (if A is neighbor of B, then B is neighbor of A)
  • No self-loops and no multiple edges between same nodes

6.1.5 Solution - DFS with Map

6.1.5.1 Walkthrough

Use DFS with a hash map to avoid re-cloning nodes:

  1. Visited map: Map<Node, Node> from original → clone. Prevents infinite recursion on cycles and reuses already-built neighbors.
  2. DFS recursion:
    • If node is null, return null.
    • If node already cloned (map.containsKey(node)), return the clone.
    • Otherwise, create a new node with the same value, store in map, then recursively clone each neighbor and append to the clone’s neighbor list.
  3. Return the clone for the starting node.

This mirrors the traversal of the original graph while reusing clones through the map.

6.1.5.2 Analysis

  • Time Complexity: O(V + E) — each edge and node is visited once.
  • Space Complexity: O(V) — hash map plus recursion stack in worst case.

6.1.5.3 Code - Java

public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }
    Map<Node, Node> map = new HashMap<>();
    return clone(node, map);
}

private Node clone(Node node, Map<Node, Node> map) {
    if (map.containsKey(node)) {
        return map.get(node);
    }
    Node copy = new Node(node.val);
    map.put(node, copy);
    for (Node neighbor : node.neighbors) {
        copy.neighbors.add(clone(neighbor, map));
    }
    return copy;
}

6.1.5.4 Code - Golang

func cloneGraph(node *Node) *Node {
    if node == nil {
        return node
    }

    cloneMap := make(map[*Node]*Node)

    return dfs(node, cloneMap)
}

func dfs(node *Node, cloneMap map[*Node]*Node) *Node {
    clone, exist := cloneMap[node]

    if exist {
        return clone
    }

    copy := &Node{Val: node.Val, Neighbors: []*Node{}}

    cloneMap[node] = copy

    for _, neighbor := range node.Neighbors {
        copy.Neighbors = append(copy.Neighbors, dfs(neighbor, cloneMap))
    }

    return copy
}

6.1.6 Solution - BFS with Map

6.1.6.1 Walkthrough

Use BFS with a queue to perform level-order traversal while maintaining a clone map:

  1. Visited map: Map<Node, Node> from original → clone. Prevents re-cloning and handles cycles.
  2. BFS with queue:
    • If node is null, return null.
    • Create initial clone, add to map, and enqueue the original node.
    • While queue not empty: dequeue node, iterate through its neighbors.
    • For each neighbor: if not yet cloned, create clone and enqueue original neighbor; append neighbor’s clone to current clone’s neighbor list.
  3. Return the clone for the starting node.

This explores the graph level-by-level, building the clone structure iteratively.

6.1.6.2 Analysis

  • Time Complexity: O(V + E) — each edge and node is visited once.
  • Space Complexity: O(V) — hash map plus queue in worst case.

6.1.6.3 Code - Java

public Node cloneGraph(Node node) {
    if (node == null) {
        return null;
    }

    Map<Node, Node> map = new HashMap<>();
    Queue<Node> queue = new LinkedList<>();

    // Clone starting node and add to queue
    Node clone = new Node(node.val);
    map.put(node, clone);
    queue.offer(node);

    while (!queue.isEmpty()) {
        Node curr = queue.poll();

        for (Node neighbor : curr.neighbors) {
            if (!map.containsKey(neighbor)) {
                // Clone neighbor and enqueue original
                map.put(neighbor, new Node(neighbor.val));
                queue.offer(neighbor);
            }
            // Add cloned neighbor to current clone's neighbors
            map.get(curr).neighbors.add(map.get(neighbor));
        }
    }

    return clone;
}

6.1.6.4 Code - Golang

func cloneGraph(node *Node) *Node {
    if node == nil {
        return node
    }

    return bfs(node)
}

func bfs(root *Node) *Node {
    cloneMap := make(map[*Node]*Node)

    queue := make([]*Node, 0)
    queue = append(queue, root)
    copyRoot := &Node{Val: root.Val, Neighbors: []*Node{}}
    cloneMap[root] = copyRoot

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]

        for _, neighbor := range current.Neighbors {
            _, visited := cloneMap[neighbor]
            if !visited {
                copyNeighbor := &Node{Val: neighbor.Val, Neighbors: []*Node{}}
                cloneMap[neighbor] = copyNeighbor
                queue = append(queue, neighbor)
            }

            // Add cloned neighbor to current clone's neighbors
            copyCurrent := cloneMap[current]
            copyNeighbor := cloneMap[neighbor]

            copyCurrent.Neighbors = append(copyCurrent.Neighbors, copyNeighbor)
        }
    }

    return copyRoot
}