Clone Graph - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const CURRENT_NODE = 'current_node', CURRENT_NODE_COLOR = 'blue';
const CLONED_NODE = 'cloned_node', CLONED_NODE_COLOR = 'orange';
const CURRENT_NEIGHBOR = 'current_neighbor', CURRENT_NEIGHBOR_COLOR = 'gold';

let originalGraph, cloneGraph;

function visMainFunction(adjList) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startPartialBatch();
    const node = getEntryNodeFromAdjList(adjList);
    if (!node) {
        notification("🚫 The input graph is empty.");
        endBatch();
        return null;
    }

    const nodeToCloneMap = new Map();
    const queue = new VisQueue().options({ labelExtractionPolicy: (node) => '' + node.val });
    const entryNodeClone = new Node(node.val);
    nodeToCloneMap.set(node, entryNodeClone);
    originalGraph.makeVisManagerForNode(node).addClass(CLONED_NODE);

    // Clone graph visualization
    cloneGraph = new VisNetworkGraph({
        nodes: [entryNodeClone],
        edges: []
    }, {
        dataPropName: 'val'
    }).options({
        layoutOptions: {
            rankdir: 'LR',
            directed: false
        }
    });

    queue.enqueue(node);
    notification(`
        🟦 <b>BFS Initialization:</b>  
        Created the first clone for the entry node (<b>${node.val}</b>) and added the original node to the BFS queue.  
        The <b>original → clone</b> mapping has been initialized in <code>nodeToCloneMap</code>.  
        When the BFS queue becomes empty, this clone of the entry node will be returned as the cloned graph’s entry point.
        <br><br>
        📘 <b>Why BFS?</b> We use <b>Breadth-First Search</b> to clone the graph level by level 
        (meaning all nodes at distance <code>n</code> from the entry node are processed before any node at distance <code>n + 1</code>),  
        ensuring each node’s clone is created before any of its neighbors are processed.  
        This guarantees that when a neighbor is later encountered,  
        the current node’s clone already exists — allowing an immediate link between them.  
        It also prevents recursion depth issues and keeps connection logic simple.
    `);
    endBatch();

    while (!queue.isEmpty()) {
        startPartialBatch();
        const current = queue.dequeue();
        const currentClone = nodeToCloneMap.get(current);

        setCurrentNodes(current, currentClone);
        notification(`
            🔍 Traversing all neighbors of ${makeColoredSpan('current node', CURRENT_NODE_COLOR)} with value <b>${current.val}</b>,  
            which has just been dequeued from the BFS queue for processing.
        `);
        endBatch();

        for (const neighbor of current.neighbors) {
            startPartialBatch();
            const neighborVM = originalGraph.makeVisManagerForNode(neighbor).addClass(CURRENT_NEIGHBOR);
            notification(`
                👀 Inspecting ${makeColoredSpan('current neighbor', CURRENT_NEIGHBOR_COLOR)} with value <b>${neighbor.val}</b>  
                to check whether it has already been cloned.  
                If not, we create its clone and enqueue it for traversal in the next BFS level.
            `);
            if (!nodeToCloneMap.has(neighbor)) {
                notification(`
                    🧬 ${makeColoredSpan('Current neighbor', CURRENT_NEIGHBOR_COLOR)} not cloned yet.  
                    Creating its clone and enqueueing it for traversal in the next BFS level.
                `);
                const neighborClone = new Node(neighbor.val);
                nodeToCloneMap.set(neighbor, neighborClone);
                queue.enqueue(neighbor);
                
                // Add new node to clone graph
                cloneGraph.addNode(neighborClone);
                neighborVM.addClass(CLONED_NODE);
                notification(`
                    ✅ Cloned ${makeColoredSpan('current neighbor', CURRENT_NEIGHBOR_COLOR)}  
                    and added it to the ${makeColoredSpan('clone graph', CLONED_NODE_COLOR)}.  
                    This ensures its clone is available for linking when other nodes encounter it later in the traversal.
                `);
            } else {
                notification(`
                    ⚪ ${makeColoredSpan('Current neighbor', CURRENT_NEIGHBOR_COLOR)} <b>${neighbor.val}</b>  
                    is already cloned — skipping cloning and reusing its existing clone for linking.
                `);
            }

            currentClone.neighbors.push(nodeToCloneMap.get(neighbor));
            cloneGraph.addEdge({
                source: currentClone,
                target: nodeToCloneMap.get(neighbor)
            });
            notification(`
                🔗 Linked the clone of ${makeColoredSpan('current neighbor', CURRENT_NEIGHBOR_COLOR)}  
                to the clone of ${makeColoredSpan('current node', CURRENT_NODE_COLOR)} in the ${makeColoredSpan('clone graph', CLONED_NODE_COLOR)}.
            `);
            neighborVM.removeClass(CURRENT_NEIGHBOR);
            endBatch();
        }

        notification(`
            ✅ Finished processing all neighbors of ${makeColoredSpan('current node', CURRENT_NODE_COLOR)} with value <b>${current.val}</b>.  
            The BFS traversal will now continue with the next node in the queue if it is not empty,  
            and will stop once the queue becomes empty.
        `);
    }

    notification(`
        ✅ <b>Cloning complete!</b> The clone graph is fully constructed.  
        Returning the <b>clone of the entry node</b> as the starting point of the new graph.
    `);
    return entryNodeClone;
}

// Node constructor
function Node(val) {
    this.val = val;
    this.neighbors = [];
}

// Visual styles
function initClassProperties() {
    setClassProperties(CURRENT_NODE, { borderColor: CURRENT_NODE_COLOR });
    setClassProperties(CURRENT_NEIGHBOR, { borderColor: CURRENT_NEIGHBOR_COLOR });
    setClassProperties(CLONED_NODE, { backgroundColor: CLONED_NODE_COLOR });
}

// Visual state tracker
let originalCurrent, cloneCurrent;

function setCurrentNodes(originalNode, cloneNode) {
    if (originalNode === originalCurrent && cloneNode === cloneCurrent) return;

    startBatch();
    originalCurrent && originalGraph.makeVisManagerForNode(originalCurrent).removeClass(CURRENT_NODE);
    cloneCurrent && cloneGraph.makeVisManagerForNode(cloneCurrent).removeClass(CURRENT_NODE);
    originalNode && originalGraph.makeVisManagerForNode(originalNode).addClass(CURRENT_NODE);
    cloneNode && cloneGraph.makeVisManagerForNode(cloneNode).addClass(CURRENT_NODE);
    originalCurrent = originalNode;
    cloneCurrent = cloneNode;
    endBatch();
}

// Build graph from input adjacency list
function getEntryNodeFromAdjList(adjList) {
    const nodes = new Map();
    const allNodes = [];
    const allEdges = [];

    for (let i = 0; i < adjList.length; i++) {
        const val = i + 1;
        const node = new Node(val);
        nodes.set(val, node);
        allNodes.push(node);
    }

    for (let i = 0; i < adjList.length; i++) {
        const node = nodes.get(i + 1);
        for (const neighborVal of adjList[i]) {
            const neighbor = nodes.get(neighborVal);
            node.neighbors.push(neighbor);
            allEdges.push({ source: node, target: neighbor });
        }
    }

    originalGraph = new VisNetworkGraph({
        nodes: allNodes,
        edges: allEdges
    }, {
        dataPropName: 'val'
    }).options({
        layoutOptions: {
            rankdir: 'LR',
            directed: false
        }
    });

    notification("🎯 <b>Original Graph</b> has been created from the input adjacency list.");
    return nodes.get(1);
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues (Color Schema)</b>
        <ul>
            <li>
            ${makeColoredSpan('Current node', CURRENT_NODE_COLOR)} —
            the original node currently dequeued from the BFS queue and being processed.
            </li>
            <li>
            ${makeColoredSpan('Current neighbor', CURRENT_NEIGHBOR_COLOR)} —
            the neighbor of the current node that is currently being processed.
            </li>
            <li>
            ${makeColoredSpan('Cloned node', CLONED_NODE_COLOR)} —
            a node whose clone has already been created and recorded in the original → clone mapping.
            </li>
        </ul>
    `);
}

Approach

We use Breadth-First Search (BFS) to traverse the original graph level by level starting from an entry node, cloning each node along with its connections as we go. Here, each level represents all nodes that are at the same shortest-path distance (in number of edges) from the entry node. The algorithm maintains a mapping between every original node and its clone to prevent redundant cloning and efficiently handle cycles in the graph.

🧩 Key Concepts

Entry Node (node): The starting point of the traversal — it corresponds to the node parameter provided in the original problem. BFS begins from this node, and its clone becomes the entry point of the cloned graph.
Original → Clone Mapping: A Map called nodeToCloneMap stores the reference between each original node and its cloned counterpart.
Queue: A BFS queue ensures nodes are processed level by level — that is, by increasing distance from the entry node.
Neighbor Linking: For every edge in the original graph, a corresponding edge is created between clones of the connected nodes.
Cycle and Structure Handling: If a neighbor has already been cloned, we reuse its existing clone instead of creating a new one. This guarantees that all connections reference the correct shared clone and so ensures that the original graph’s structure is preserved — and also naturally prevents infinite loops during traversal of cyclic graphs.

🔁 Step-by-Step Process

Initialization:
- Create the first clone for the entry node.
- Add the original node to the BFS queue and map it to its clone in nodeToCloneMap.
BFS Traversal:
- Dequeue a node (called the current node).
- For each of its neighbors:
Termination:
- When the queue becomes empty, all nodes and their connections have been cloned.
- Return the clone of the entry node — it serves as the entry point to the fully cloned graph.

📘 Why BFS?

BFS processes the graph level by level — meaning all nodes at distance n from the entry node are processed before any node at distance n + 1. This ensures that each node’s clone is created before its neighbors are visited, so when a neighbor is later encountered, its clone already exists and can be linked immediately.

Time Complexity

Let V be the number of nodes and E be the number of edges in the connected component reachable from the entry node.

Each node is enqueued and dequeued at most once in BFS, so processing all nodes costs O(V).
Each edge is inspected twice in total — once from each endpoint: once when exploring one node and once again when its neighbor is later encountered, but the second time it is immediately skipped since that neighbor has already been visited. Thus, edge processing still costs O(E).

Therefore, the overall time complexity is O(V + E).

Space Complexity

Let V be the number of nodes and E be the number of edges in the connected component reachable from the entry node.

A Map (nodeToCloneMap) stores one entry per node, requiring O(V) space.
The BFS queue can temporarily hold up to all nodes at the widest level of traversal — in the worst case, this also reaches O(V).
The cloned graph itself occupies O(V + E) space, but this is the output. Excluding the output, the auxiliary memory includes only references to the nodes in the map and queue, totaling O(V). (The edges are stored as part of the cloned nodes’ neighbor lists, contributing only to the output space.)

Therefore, the auxiliary space complexity (excluding input and output) is O(V), while the total space complexity (including the cloned graph output) is O(V + E).

Input-1

Clone Graph - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

🧩 Key Concepts

🔁 Step-by-Step Process

📘 Why BFS?

Time Complexity

Space Complexity