Clone Graph

                                            
var cloneGraph = function(node) {
    if (!node) return node;

    const visited = new Map();

    const dfs = (node) => {
        if (visited.has(node)) {
            return visited.get(node);
        }

        const clonedNode = new Node(node.val);
        visited.set(node, clonedNode);

        for (let neighbor of node.neighbors) {
            clonedNode.neighbors.push(dfs(neighbor));
        }

        return clonedNode;
    }

    return dfs(node);
};

                                            
/**
 * Definition for Node.
 * 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) return null;
    
    const visited = new Map<Node, Node>();
    
    const dfs = (current: Node | null): Node | null => {
        if (!current) return null;
        
        if (visited.has(current)) {
            return visited.get(current);
        }
        
        const clonedNode = new Node(current.val);
        visited.set(current, clonedNode);
        
        clonedNode.neighbors = current.neighbors.map(neighbor => dfs(neighbor));
        
        return clonedNode;
    }
    
    return dfs(node);
};

                                            
/**
 * Definition for a Node.
 * class Node {
 *     public $val = null;
 *     public $neighbors = null;
 *     function __construct($val = 0) {
 *         $this->val = $val;
 *         $this->neighbors = array();
 */
class Solution {
    public $map = [];
    function cloneGraph($node) {
        if ($node == null) return $node;
        
        if (isset($this->map[$node->val])) {
            return $this->map[$node->val];
        }
        
        $newNode = new Node($node->val);
        $this->map[$node->val] = $newNode;
        
        foreach ($node->neighbors as $neighbor) {
            $newNode->neighbors[] = $this->cloneGraph($neighbor);
        }
        
        return $newNode;
    }
}

                                            
/**
 * Definition for a Node.
 * class Node(var `val`: Int) {
 *     var neighbors: ArrayList<Node?> = ArrayList<Node?>()
 * }
 */
class Solution {
    private val map = HashMap<Int, Node>()
    
    fun cloneGraph(node: Node?): Node? {
        if (node == null) return null
        
        if (map.containsKey(node.`val`)) {
            return map[node.`val`]
        }
        
        val newNode = Node(node.`val`)
        map[node.`val`] = newNode
        
        node.neighbors.forEach {
            newNode.neighbors.add(cloneGraph(it))
        }
        
        return newNode
    }
}

                                            
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Neighbors []*Node
 * }
 */

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    visited := make(map[*Node]*Node)
    return clone(node, visited)
}

func clone(node *Node, visited map[*Node]*Node) *Node {
    if _, ok := visited[node]; ok {
        return visited[node]
    }

    newNode := &Node{Val: node.Val}
    visited[node] = newNode

    for _, neighbor := range node.Neighbors {
        newNode.Neighbors = append(newNode.Neighbors, clone(neighbor, visited))
    }

    return newNode
}

                                            
import scala.collection.mutable

object Solution {
  def cloneGraph(node: Node): Node = {
    if (node == null) return null

    val visited = mutable.Map[Int, Node]()

    def cloneHelper(node: Node): Node = {
      if (visited.contains(node.value)) {
        return visited(node.value)
      }

      val cloneNode = new Node(node.value)
      visited(node.value) = cloneNode

      cloneNode.neighbors = node.neighbors.map(cloneHelper)

      cloneNode
    }

    cloneHelper(node)
  }
}

To solve this coding challenge, we will implement a function to deep copy an undirected graph. The graph is represented using an adjacency list, and each node in the graph has a value and a list of neighbor nodes. Our goal is to return a deep copy of the graph, meaning that each node and its connections will be duplicated without sharing any reference with the original graph.

Explanation

In this challenge, we need to ensure that each node and its corresponding neighbors are copied correctly in such a way that the copied graph is identical to the original graph but without any shared references. We will employ Depth-First Search (DFS) to traverse the graph and clone each node. A crucial part of this process is maintaining a map (or dictionary) to record which original nodes have already been cloned, thus preventing infinite loops due to the cyclic nature of graphs. Here’s a step-by-step breakdown of our approach:

Check for the Null Input:

If the input node is

null

, we immediately return

null

since there is no graph to clone.

Use a Dictionary to Keep Track:

We use a dictionary named

visited

to map each original node to its clone. This helps to avoid re-cloning the same node and keeps track of already visited nodes.

Depth-First Search (DFS) function:

We define a recursive DFS function that will:

Check if the current node has already been cloned by looking it up in the
visited

dictionary.
If it is already cloned, return the clone from the dictionary.
If it is not yet cloned, create a new node, add it to the
visited

dictionary, and then recursively clone all its neighbors.

Clone the Graph:

Use the DFS function to start cloning from the given initial node.

Below is the pseudocode, including comments to explain each step:

                                            
# Function to clone the graph
function cloneGraph(node):
# If the given node is null, return null as there is no graph to clone
if node is null:
return null

# Dictionary to keep track of visited nodes and their clones
visited = dictionary()

# Depth-First Search (DFS) function to clone the graph
function DFS(currentNode):
# If the current node is already visited, return its clone from visited dictionary
if currentNode in visited:
return visited[currentNode]

# Create a clone for the current node
clonedNode = Node(currentNode.val)
# Add the cloned node to the visited dictionary
visited[currentNode] = clonedNode

# Iterate through all the neighbors of the current node
for neighbor in currentNode.neighbors:
# Recursively clone the neighbors and add them to the clone's neighbors list
clonedNode.neighbors.append(DFS(neighbor))

# Return the cloned node
return clonedNode

# Start cloning process from the input node using DFS
return DFS(node)

Detailed Steps in Pseudocode

Initialization:

Begin by checking if the provided

node

null

. If it is, return

null

Dictionary Setup:

Initialize an empty dictionary called

visited

which will store mappings from original nodes to their clones.

Define DFS Function:

This function takes a
currentNode

.
If
currentNode

exists in
visited

, it means the node is already cloned, so return the corresponding clone from the dictionary.
If not, create a new node (
clonedNode

) with the same value as
currentNode

.
Add the new
clonedNode

to the
visited

dictionary with
currentNode

as the key.
For each neighbor of
currentNode

, call DFS recursively and append the result to the
clonedNode

's neighbors list.
Return the
clonedNode

.

Start DFS Cloning:

Call the DFS function with the initial input

node

and return the result.

By carefully managing the

visited

dictionary, we ensure each node is only cloned once, efficiently handling cycles in the graph while maintaining the structure and connections of the original graph in the newly cloned graph.