Clone Graph medium

Problem Statement

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (val) and a list (neighbors) of its neighbors.

Example 1

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. Node 1 has neighbors 2 and 4. Node 2 has neighbors 1 and 3. Node 3 has neighbors 2 and 4. Node 4 has neighbors 1 and 3.

Example 2

Input: adjList = [[]] Output: [[]] Explanation: Node 0 is connected to no node

Steps

1. Create a Visited Map: Use a Map to store visited nodes and their corresponding cloned nodes. This prevents infinite loops and ensures we don't clone nodes multiple times.

2. DFS (Depth-First Search): Perform a depth-first search on the graph. For each node:

   • Check if the node has already been visited (in the visited map). If it has, return its clone.
   • Create a new node with the same val.
   • Recursively clone each neighbor of the current node.
   • Add the cloned neighbors to the neighbors list of the cloned node.
   • Add the cloned node to the visited map.

3. Return the Clone: After the DFS, the visited map will contain all the cloned nodes. Return the clone of the root node.

Explanation

The key to solving this problem efficiently is to avoid revisiting nodes and creating duplicate clones. The visited map acts as a cache, allowing us to quickly retrieve the clone of a node if we've already processed it. The recursive DFS ensures that all connected nodes are explored and cloned.

Code

class Node {
    val: number;
    neighbors: Node[];
    constructor(val?: number, neighbors?: Node[]) {
        this.val = val === undefined ? 0 : val;
        this.neighbors = neighbors === undefined ? [] : neighbors;
    }
}

function cloneGraph(node: Node | null): Node | null {
    if (node === null) return null;

    const visited = new Map<Node, Node>(); // Map to store visited nodes and their clones

    function dfs(node: Node): Node {
        if (visited.has(node)) {
            return visited.get(node)!; // Return the cloned node if already visited
        }

        const clone = new Node(node.val); // Create a new node
        visited.set(node, clone); // Add the node to the visited map

        for (const neighbor of node.neighbors) {
            clone.neighbors.push(dfs(neighbor)); // Recursively clone neighbors
        }

        return clone;
    }

    return dfs(node);
}

//Example usage
const node1 = new Node(1);
const node2 = new Node(2);
const node3 = new Node(3);
const node4 = new Node(4);

node1.neighbors = [node2, node4];
node2.neighbors = [node1, node3];
node3.neighbors = [node2, node4];
node4.neighbors = [node1, node3];


const clonedGraph = cloneGraph(node1);

//Verification (optional - depends on how you want to verify the cloned graph)
console.log("Original Graph Node 1 Neighbors:", node1.neighbors.map(n => n.val));
console.log("Cloned Graph Node 1 Neighbors:", clonedGraph!.neighbors.map(n => n.val));

Complexity

• Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges in the graph. This is because we visit each node and edge once.

• Space Complexity: O(V), mainly due to the visited map which stores at most V nodes. The recursive call stack can also contribute to space complexity, but it's bounded by the height of the graph, which is at most V in the worst case (a very deep graph).