Start learning free

LESSON 572 OF 671 · GRAPHS

Clone Graph in JavaScript: BFS with a Map of Copies

Practice O(V + E) Read the full explanation

You get node 1 of an undirected graph. The graph has n nodes with the values 1 to n. Each Node holds its value and a list of its neighbors. Its class is in the starter code.

Make a deep copy of the whole graph, and return the copy's node 1:

  • Make n new nodes, one per original node, with the same values.
  • Give each new node the copies of the original's neighbors, in the same order.
  • Never put an original node into the copy.

An empty graph (n = 0) comes as null. Return null for it.

The examples write a graph as adjacency lists. Entry i - 1 of adjList lists the values of node i's neighbors. The tests walk your copy from the node you return. They print each node's neighbors. They also flag any node that belongs to the original graph.

 

Example 1:

Input: adjList = [[2, 3], [1, 3], [1, 2, 4], [3, 5], [4]]
Output: [[2, 3], [1, 3], [1, 2, 4], [3, 5], [4]]
Explanation: Five nodes: a triangle with a tail.
    1 - 2
     \ /
      3 - 4 - 5
The copy has the same shape, built from 5 new nodes.

Example 2:

Input: adjList = [[2], [1]]
Output: [[2], [1]]
Explanation: Two nodes joined by one edge.
Each new node lists the other new node.

Example 3:

Input: adjList = [[3], [3], [1, 2]]
Output: [[3], [3], [1, 2]]
Explanation: Node 2 is not a neighbor of node 1.
The copy reaches it only through node 3.

 

Constraints:

  • 0 to 50,000 nodes.
  • Node i has the value i.
  • Up to 100,000 edges.
  • No edge joins a node to itself.
  • No two edges join the same two nodes.
  • Every node can be reached from node 1.

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. It 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. That is also when the node joins the queue. When a node leaves the queue, the copies of its neighbors are added to its copy's list. The map stops the search from going around a cycle forever. A node that already has a copy is never copied or queued again. A recursive DFS with the same map works too.

STEP 1 OF 14
    Ctrl + Enter to check

    JAVASCRIPT · GRAPHS

    Clone Graph in JavaScript, explained

    Problem overview

    The method cloneGraph(node) receives node 1 of a connected, undirected graph and returns a deep copy of the graph: the copy of node 1. Each node holds a value, val, and an array of its neighbors, neighbors. The lesson provides the node class in a comment above the starter code, as the constructor function Node(val), which sets this.val and starts this.neighbors as an empty array. The graph has n nodes, 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, one per original node, with the same values. The neighbor array 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. When the graph is empty, node is null, and the method returns null.

    For the square adjList = [[2, 4], [1, 3], [2, 4], [1, 3]], meaning 1 is joined to 2 and 4, 2 to 1 and 3, and so on, the copy has four new nodes joined in the same square. For [[]] the copy is one new node with no neighbors, and for [] the answer is null.

    The lesson asks for O(V + E) time and O(V) extra space, where V is the number of nodes and E the number of edges.

    Approach: a map from each original node to its copy

    Copying one node is easy. The difficulty is the links. A node's neighbors link back to it, so the graph is full of cycles, and a naive recursive copy would copy node 1, then its neighbor 2, then 2's neighbor 1 again, and never stop. It would also create two copies of the same node.

    The fix is a Map from each original node to its copy. It does two jobs: it finds the copy of any node met so far, and it tells which nodes have been met already. The search is a breadth-first search (BFS):

    • A node's copy is made the first time the search meets the node. That is also the moment the node joins the queue.
    • When a node leaves the queue, each of its neighbors is looked at. A neighbor without a copy gets one and is queued. Then the copy of the neighbor is appended to the neighbor array of the current node's copy.

    A node that already has a copy is never copied or queued again, which is what stops the search from going around a cycle forever. A recursive DFS with the same map would also work.

    The tests on this lesson walk the copy and check two things: that the neighbor lists have the right values in the right order, and that no node of the copy is a node of the original. For the square, the copy has the same lists, [[2, 4], [1, 3], [2, 4], [1, 3]], and shares none of the four nodes with the original.

    Step by step

    1. Handle the empty graph. If node === null, return null. The next lines read the node's value, which needs a node.
    2. Create the map. copies = new Map() maps each original node to its copy. A Map can use objects as keys and compares them by identity, so two different nodes are two different keys even if their values were equal. A plain object can't do this, because its keys are strings.
    3. Copy the first node. copies.set(node, new Node(node.val)). The copy starts with an empty neighbor array.
    4. Start the queue as an array holding just node. Every node in the queue already has a copy; what its copy still lacks is its neighbor array.
    5. Keep an index head, declared with let and starting at 0, for the next node to take from the queue. Moving an index forward is cheaper than shift(), which would move every remaining element each time.
    6. Loop while head < queue.length: some nodes are still waiting.
    7. Take the current node, queue[head], and then do head++.
    8. Loop over current.neighbors with for...of. Over the whole run each edge is looked at twice, once from each end.
    9. If !copies.has(neighbor), the search is meeting this node for the first time. Make its copy with copies.set(neighbor, new Node(neighbor.val)) and push neighbor onto the queue. This is the only place a copy is made, so each node is copied once and queued once.
    10. Link the copies. Push copies.get(neighbor) onto copies.get(current).neighbors. The copy of current points to the copy of neighbor, never to the original. The neighbors arrive in the order of the original array, so each copied array keeps the original order.
    11. Return copies.get(node), the copy of node 1. The graph is connected, so every node was reached.

    The solution in JavaScript

    class Solution {
        cloneGraph(node) {
            if (node === null) {
                return null;
            }
            const copies = new Map();
            copies.set(node, new Node(node.val));
            const queue = [node];
            let head = 0;
            while (head < queue.length) {
                const current = queue[head];
                head++;
                for (const neighbor of current.neighbors) {
                    if (!copies.has(neighbor)) {
                        copies.set(neighbor, new Node(neighbor.val));
                        queue.push(neighbor);
                    }
                    copies.get(current).neighbors.push(copies.get(neighbor));
                }
            }
            return copies.get(node);
        }
    }
    

    JavaScript details worth knowing:

    • Objects as keys. A Map keeps the key as it is. With a plain object, o[a] = 1; o[b] = 2 turns both nodes into the same string key "[object Object]", so the second assignment overwrites the first. Likewise, map.get({}) is undefined after map.set({}, 2), because the two {} are different objects. The lookups in this solution work because they use the very same node objects as keys.
    • new Node(val). Node is a constructor function that the lesson provides. Calling it with new makes an object with val set and an empty neighbors array. Each call makes a new array, so the copies don't share neighbor arrays.
    • === with null. node === null is true only for null. It's the right test here because the empty graph is passed as null.
    • Reference types. Pushing neighbor instead of copies.get(neighbor) would make a copy that points into the original graph. The array would look right when printed, but the lesson's tests would report nodes of the original in the copy.

    Complexity

    Time: O(V + E). Each node is copied once and queued once, and each edge is looked at twice, once from each end. Map operations take constant time on average.

    Space: O(V) extra. The map and the queue each hold at most one entry per node. The copy itself, which is the output, takes O(V + E).

    Edge cases and common mistakes

    • The empty graph. cloneGraph(null) must return null. Without the first check, node.val would throw.
    • A single node. [[]] gives a copy with value 1 and no neighbors, and the copy is a different object from the original.
    • Making copies at the wrong moment. Creating a copy every time a node is seen as a neighbor gives several copies of one node and breaks the links. A copy is created only when copies.has(neighbor) is false.
    • Queuing nodes twice. Queuing a neighbor outside the if would let the search loop around a cycle forever.
    • Returning the original. The method must return copies.get(node), not node. For the square graph, the returned node is a different object and none of the four nodes are shared.
    • A chain such as [[2], [1, 3], [2]]. Node 2 is a neighbor of both 1 and 3, but gets exactly one copy, and both of its neighbors' copies link to it.

    Testing

    • adjList = [[2, 4], [1, 3], [2, 4], [1, 3]] gives a copy with the lists [[2, 4], [1, 3], [2, 4], [1, 3]] and no shared nodes.
    • adjList = [[]] gives [[]], a single new node.
    • adjList = [] gives null.
    • adjList = [[2], [1, 3], [2]] gives [[2], [1, 3], [2]] with three new nodes.
    Keep going with JavaScript650+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free