☕ DSA Java Articles

Topics › Graphs › Problems on BFS/DFS

Clone Graph

Medium TUF ID 188 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a reference to one node of a connected, undirected graph. Every node stores an integer val and a list neighbors of the nodes it is joined to. Return a deep copy of the whole graph: a brand-new set of nodes with the same values and the same connections, where no pointer in the copy leads back into the original.

On LeetCode the graph is described by an adjacency list in which adj[i] lists the neighbours of the node whose value is i + 1, and the node you receive is the one with value 1. An empty list means the graph is empty and the input node is null.

Constraints: 0 ≤ n ≤ 100, values are unique and lie in 1..n, there are no self-loops or repeated edges, and the graph is connected.

The Java file uses this node type:

static class Node {
    int val;
    List<Node> neighbors = new ArrayList<>();
    Node(int val) { this.val = val; }
}

Example 1

adj = [[2,4],[1,3],[2,4],[1,3]]
answer: a new 4-cycle 1-2-3-4-1 with the same adjacency lists

Node 1 touches 2 and 4, node 2 touches 1 and 3, and so on. The copy must have four new node objects wired the same way.

Example 2

adj = [[]]
answer: a single new node with value 1 and no neighbours

There is no edge to follow, so the copy is one isolated node. (For adj = [] the answer is null.)

Two things make this harder than copying a linked list. First, cycles: a naive “copy this node, then recursively copy each neighbour” runs forever on 1 -> 2 -> 1, because nothing tells it that node 1 is already being copied. Second, sharing: in example 1, node 3 is reachable from both 2 and 4, and the copy must contain exactly one node 3, not two. Both problems have the same cure: remember, for every original node, the copy you made for it.

Approach 1: Two passes, find every node then wire the edges

Intuition. Split the job into “which nodes exist” and “how they are connected”. If every copy already exists before we add a single edge, cycles and shared neighbours stop being a problem: for any original edge a - b we simply look up the copies of a and b and connect them. So first walk the graph once to collect all original nodes, create one copy per node in a map original -> copy, and then walk the collected list a second time to fill the neighbour lists.

Algorithm.

  1. If the input is null, return null.
  2. BFS from the input node with a seen set, appending each node to a list all as it is dequeued.
  3. For each node in all, put original -> new Node(original.val) into the map.
  4. For each original node, and for each of its neighbours nb, append copy.get(nb) to the copy’s neighbour list.
  5. Return the copy of the input node.
static Node twoPass(Node node) {
    if (node == null) return null;
    List<Node> all = new ArrayList<>();
    Set<Node> seen = new HashSet<>();
    Deque<Node> queue = new ArrayDeque<>();
    seen.add(node);
    queue.add(node);
    while (!queue.isEmpty()) {                       // pass 1: find every original node
        Node cur = queue.poll();
        all.add(cur);
        for (Node nb : cur.neighbors) {
            if (seen.add(nb)) queue.add(nb);
        }
    }
    Map<Node, Node> copy = new HashMap<>();
    for (Node orig : all) copy.put(orig, new Node(orig.val));
    for (Node orig : all) {                          // pass 2: copy each adjacency list
        Node c = copy.get(orig);
        for (Node nb : orig.neighbors) c.neighbors.add(copy.get(nb));
    }
    return copy.get(node);
}

Complexity. Time O(V + E): each pass touches every node once and every adjacency entry once. Space O(V) for seen, the list, the map and the queue, not counting the clone itself.

This is already optimal in big-O terms. Its only weakness is that it walks the graph twice and keeps an extra list and set. The next two approaches fold everything into one traversal, using the map as the visited set.

Approach 2: One-pass DFS with a map

Intuition. The map original -> copy can do double duty. If a node is in the map, it has been visited and its copy exists. So a recursive function dfs(node) can work like this: if the node is already in the map, return its copy; otherwise create the copy, store it, and fill its neighbour list by calling dfs on each neighbour.

The order of those last two steps is the whole trick. The copy must be stored in the map before recursing. When the recursion goes 1 -> 2 -> 1, the inner call for node 1 must find the half-built copy of 1 and return it immediately. If we stored the copy only after the loop, that inner call would create a second copy of node 1 and recurse again, forever.

Algorithm.

  1. dfs(null) returns null.
  2. If node is in the map, return the stored copy.
  3. Create c = new Node(node.val) and store node -> c.
  4. For each neighbour nb, append dfs(nb) to c.neighbors.
  5. Return c.
static Node cloneDfs(Node node) {
    return dfs(node, new HashMap<>());
}

static Node dfs(Node node, Map<Node, Node> copy) {
    if (node == null) return null;
    Node done = copy.get(node);
    if (done != null) return done;                   // already copied: reuse it, this closes cycles
    Node c = new Node(node.val);
    copy.put(node, c);                               // register BEFORE recursing into neighbours
    for (Node nb : node.neighbors) c.neighbors.add(dfs(nb, copy));
    return c;
}

Dry run on example 1 (1:[2,4], 2:[1,3], 3:[2,4], 4:[1,3]; primes mark copies):

step call what happens
1 dfs(1) create 1’, store it, recurse into neighbour 2
2 dfs(2) create 2’; neighbour 1 is in the map, append 1’; recurse into 3
3 dfs(3) create 3’; neighbour 2 is in the map, append 2’; recurse into 4
4 dfs(4) create 4’; append 1’ and 3’ (both in the map); return 4’
5 back in 3 append 4’, so 3’ = [2’, 4’]; return 3’
6 back in 2 append 3’, so 2’ = [1’, 3’]; return 2’
7 back in 1 append 2’; neighbour 4 is in the map, append 4’; 1’ = [2’, 4’]

Each original node produced exactly one copy, and every neighbour list keeps its original order.

Complexity. Time O(V + E): each node is created once, and each adjacency entry triggers one call that either returns from the map or does real work once. Space O(V) for the map plus O(V) recursion depth in the worst case (a long path).

Approach 3: One-pass BFS with a map

Intuition. The same map-as-visited idea works with a queue instead of the call stack, which removes any risk of a stack overflow on a long, path-like graph. Create a node’s copy the first time it is seen as somebody’s neighbour, and enqueue the original. When a node is later dequeued, its copy already exists, and so do the copies of any neighbours already seen; the ones not yet seen are created on the spot. Either way, appending the neighbour’s copy is always possible.

Algorithm.

  1. If the input is null, return null.
  2. Copy the input node, store it in the map, and enqueue the original.
  3. While the queue is not empty, dequeue cur and fetch its copy c.
  4. For each neighbour nb: if it has no copy yet, create one, store it, and enqueue nb. Append the copy of nb to c.neighbors.
  5. Return the copy of the input node.
static Node cloneBfs(Node node) {
    if (node == null) return null;
    Map<Node, Node> copy = new HashMap<>();
    copy.put(node, new Node(node.val));
    Deque<Node> queue = new ArrayDeque<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        Node c = copy.get(cur);
        for (Node nb : cur.neighbors) {
            Node nbCopy = copy.get(nb);
            if (nbCopy == null) {                    // first sighting: create it and schedule a visit
                nbCopy = new Node(nb.val);
                copy.put(nb, nbCopy);
                queue.add(nb);
            }
            c.neighbors.add(nbCopy);
        }
    }
    return copy.get(node);
}

Complexity. Time O(V + E): each node is enqueued once, and each adjacency entry costs one map lookup and one append. Space O(V) for the map and the queue.

Each undirected edge a - b is stored twice, once in a’s list and once in b’s list, and each of those two entries is copied once when its owner is dequeued. So the clone ends up with exactly the same edge set as the original, with no duplicates and none missing.

Edge cases and pitfalls