Start learning free

LESSON 477 OF 536 · GRAPHS

Clone Graph in Java: BFS with a HashMap in O(V + E)

Practice O(V + E) Read the full explanation

You are given node 1 of a connected, undirected graph. Return a deep copy (a clone) of the graph.

Each node holds a value and the list of its neighbors; the node class is shown in the starter code. The graph has n nodes, numbered from 1 to n, and node i has the value i. The graph is connected, so every node can be reached from node 1 by going from neighbor to neighbor.

A deep copy is made of exactly n brand-new nodes, one for each node of the graph, with the same value. The neighbor list of each new node holds the new nodes of the original node's neighbors, in the same order. No node of the copy may be a node of the original graph. Return the new node 1. If the graph is empty (n = 0), you get null and return null.

The examples show a graph by its adjacency lists: adjList[i - 1] holds the values of node i's neighbors. After your function returns, the tests walk your copy from the node you returned, print the neighbors of each node, node by node, and report any node that belongs to the original graph.

 

Example 1:

Input: adjList = [[2, 4], [1, 3], [2, 4], [1, 3]]
Output: [[2, 4], [1, 3], [2, 4], [1, 3]]
Explanation: The graph has 4 nodes, joined in a square:
    1 - 2
    |   |
    4 - 3
Node 1's neighbors are nodes 2 and 4, node 2's are nodes 1 and 3, node 3's are nodes 2 and 4,
and node 4's are nodes 1 and 3. The copy has the same shape, made of 4 new nodes.

Example 2:

Input: adjList = [[]]
Output: [[]]
Explanation: The graph is a single node, node 1, with no neighbors. The copy is one new node with the value 1.

Example 3:

Input: adjList = []
Output: []
Explanation: The graph is empty: the function gets null and returns null.

 

Constraints:

  • 0 <= n <= 5 * 104
  • Node i has the value i, for 1 <= i <= n.
  • There are at most 105 edges. No edge joins a node to itself, and no edge appears twice.
  • The graph is connected.

Note:

Your algorithm should run in O(V + E) time, where V is the number of nodes and E the number of edges, and use O(V) extra space.

The tutorial walks the graph with a BFS, as in Course Schedule, and keeps a hash map from each original node to its copy. A node's copy is made the first time the search meets the node, and that is also when the node joins the queue. When a node leaves the queue, the copies of its neighbors are appended to its copy's list. The map is what stops the search from going around a cycle forever: a node that already has a copy is never made or queued again. A recursive DFS with the same map works too.

STEP 1 OF 13
    Ctrl + Enter to check

    JAVA · GRAPHS

    Clone Graph in Java, explained

    Problem overview

    The method cloneGraph receives node, node 1 of a connected, undirected graph, and returns a deep copy of the graph: the copy of node 1. The lesson provides the Node class, with a public int val, a List<Node> neighbors and a constructor Node(int val) that creates an empty neighbor list. Node i has the value i, and every node can be reached from node 1.

    A deep copy is made of exactly n brand-new nodes with the same values. The neighbor list of each new node holds the new nodes of the original node's neighbors, in the same order. No node of the copy may be a node of the original graph. When the graph is empty, node is null and the method returns null.

    The examples show a graph as adjacency lists, where entry i - 1 holds the values of node i's neighbors. For [[2, 4], [1, 3], [2, 4], [1, 3]], the graph is a square of four nodes (1-2-3-4-1), and the copy is a new square with the same neighbor order. For [[]] the graph is a single node with no neighbors, and the copy is one new node with value 1. For [] the method receives null and returns null.

    The statement asks for O(V + E) time and O(V) extra space, with up to 50,000 nodes and 100,000 edges.

    Approach: BFS and a map from original to copy

    The difficulty is that graphs have cycles and shared neighbors. If you copy a node by copying each neighbor recursively, you run around a cycle forever, and a node that is a neighbor of two nodes would be copied twice. The fix is a HashMap from each original node to its copy. It does two jobs: it finds the copy of any node met so far, and its keys tell which nodes have been met already.

    The search is a breadth-first search. A node's copy is made the first time the search meets the node, and that is also when the node joins the queue. A node that already has a copy is never copied or queued again, which stops the search from looping through a cycle. Every node in the queue already has its copy. What the copy still lacks is its neighbor list, which is filled in when the node leaves the queue: for each neighbor, append the neighbor's copy to the list of the current node's copy.

    Since the neighbors are visited in the original order, each copied list keeps that order. A recursive DFS with the same map would work as well. The BFS version uses a queue instead of the call stack, which is safer on a path of 50,000 nodes.

    Step by step

    1. Handle the empty graph. If node is null, return null. The next lines read node.val, which needs a node.
    2. Create copies, a Map<Node, Node> backed by a HashMap. Node doesn't define equals or hashCode, so the map compares nodes by identity: two different nodes are two different keys, even with the same value.
    3. Put the first entry: node maps to new Node(node.val).
    4. Create queue, a Deque<Node> backed by an ArrayDeque. It holds nodes whose neighbors still have to be copied.
    5. Add node to the queue.
    6. Loop while the queue isn't empty. The search ends when every reachable node has been taken from the queue.
    7. Take the front node with poll into current. Now its copy's neighbor list gets filled.
    8. Loop over current.neighbors with an enhanced for. Over the whole run each edge is looked at twice, once from each end.
    9. Check !copies.containsKey(neighbor): no copy yet means the search meets this node for the first time.
    10. Make the copy: put neighbor in copies, mapped to new Node(neighbor.val).
    11. Add neighbor to the queue. A node joins the queue only when its copy is made, so each node is queued once.
    12. Link the copies after the if, still inside the loop: add copies.get(neighbor) to copies.get(current).neighbors. The copy of current points to the copy of neighbor, never to neighbor itself.
    13. Return copies.get(node), the copy of node 1.

    The solution in Java

    class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> copies = new HashMap<>();
        copies.put(node, new Node(node.val));
        Deque<Node> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            for (Node neighbor : current.neighbors) {
                if (!copies.containsKey(neighbor)) {
                    copies.put(neighbor, new Node(neighbor.val));
                    queue.add(neighbor);
                }
                copies.get(current).neighbors.add(copies.get(neighbor));
            }
        }
        return copies.get(node);
    }
}

    The Java details worth a closer look:

    • Identity keys. Without equals and hashCode overrides, a class inherits Object's versions, which compare references. Two Node objects with the same val are two different keys: putting two such nodes in a HashMap leaves two entries. That is exactly what this algorithm needs, because the key must be the original node object, not its value.
    • Deque and ArrayDeque. add puts a node at the back and poll takes the one at the front, which makes a first-in, first-out queue. ArrayDeque is the usual choice and doesn't accept null elements. poll returns null when the queue is empty, which is why the loop tests isEmpty() first.
    • Diamond operator. new HashMap<>() lets the compiler fill in the type arguments from the declared type. The lesson's editor already provides java.util. In a file of your own, add import java.util.*;.
    • References. copies.get(current) returns the same copy object every time, so adding to its neighbors list changes that one node. Nothing is duplicated by accident.
    • Declare against the interface. Using Map and Deque as the variable types keeps the code independent of the concrete classes.

    Complexity

    Each node is copied once and queued once. Each edge is examined twice, once from each end, and each examination does a constant number of hash lookups on average. The time is O(V + E). The map holds one entry per node, and the queue never holds more than V nodes, so the extra space is O(V), not counting the copy itself.

    Edge cases and common mistakes

    • Empty graph. A null input must return null. Skipping the check throws a NullPointerException on node.val.
    • A single node. The loop runs once with no neighbors, and the result is one new node with an empty list.
    • Linking to the original neighbor. Writing neighbors.add(neighbor) instead of copies.get(neighbor) builds a copy that still points into the original graph, which the lesson's tests report.
    • Copying a node twice. Without the containsKey check, nodes reachable by two paths get two copies, and cycles never end.
    • Checking the map but not queueing. A node that gets a copy but is never added to the queue ends up with an empty neighbor list.
    • Neighbor order. The copies' lists must keep the original order. Iterating the original list in order and appending guarantees that.

    Testing

    These results come from running the solution on graphs written as adjacency lists. In every case the copy had the same neighbor lists and contained none of the original nodes, and a path of 50,000 nodes, the largest size the statement allows, was copied in full.

    Adjacency listNeighbors in the copy
    [[2, 4], [1, 3], [2, 4], [1, 3]][[2, 4], [1, 3], [2, 4], [1, 3]]
    [[]][[]]
    [][] (the method returned null)
    [[2, 3], [1, 3], [1, 2]][[2, 3], [1, 3], [1, 2]]
    [[3, 2], [1], [1]][[3, 2], [1], [1]]
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free