Clone Graph

Problem Statement

In this task, you are given a reference to a node in a connected undirected graph. The objective is to create a deep copy (clone) of the graph. Each node in the graph comprises an integer value and a list of its neighboring nodes, structured within a class Node consisting of an integer val and a List<Node> for neighbors. The cloned graph must maintain the structure and connectivity of the original graph, with separate but identical nodes and relationships.

Examples

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.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

Example 2

Input:

adjList = [[]]

Output:

[[]]

Explanation:

Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

Example 3

Input:

adjList = []

Output:

[]

Explanation:

This an empty graph, it does not have any nodes.

Constraints

• The number of nodes in the graph is in the range [0, 100].
• 1 <= Node.val <= 100
• Node.val is unique for each node.
• There are no repeated edges and no self-loops in the graph.
• The Graph is connected and all nodes can be visited starting from the given node.

Approach and Intuition

When approaching the problem of cloning a graph, the main challenge is to create an exact replica of the nodes and their interconnections without sharing reference to the original nodes. Given the nature of graphs, care must be taken to handle possible cycles and repetitions through the connections. Here's how our solution can be structured:

1. Identify Node Existence: If the graph is empty (null reference provided), immediately return null for the clone.

2. Utilizing Hash Map for Clone Mapping: A hash map can be effective in tracking original nodes and their corresponding cloned versions. This structure will help ensure that each original node has a unique clone and supports the quick lookup to avoid duplicates and handle cyclic references.

3. Depth-First Search Implementation: Employ a depth-first search (DFS) to explore all nodes starting from the given node. For each node encountered:

   • Check if it’s already cloned (exists in the hash map); if not, create a clone, add it to the hash map and proceed to clone its neighbors.
   • Add the cloned neighbors to the cloned node's neighbors list.

4. Iterate through Neighbors: Recursively apply the above approach to all neighbors of the current node, which ensures that the entire graph is traversed and cloned.

5. Return Cloned Graph: The hash map or a direct reference from the first visited node would provide the entry point to the fully cloned graph.

Insights from Examples:

• Example 1: Shows a simple graph with 4 nodes interconnected. Each node points to two other nodes forming a cycle. Our cloning method needs to retain these connections accurately.
• Example 2 and Example 3: These are edge cases demonstrating scenarios with the smallest possible graphs - one empty graph and another with a single node with no neighbors. This highlights the importance of handling graphs with minimum elements appropriately in your implementation to avoid null reference issues.

Armed with these strategies, it is possible to reliably clone any connected undirected graph by effectively utilizing data structures like hash maps for node reference management and recursive traversal techniques like DFS for thorough graph exploration.

Solutions

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return nullptr;
        }
        // Using an unordered map to store cloned nodes
        unordered_map<Node*, Node*> cloneMap;
        // Initialize the BFS queue
        queue<Node*> q;
        q.push(node);
        // Creating the initial clone
        cloneMap[node] = new Node(node->val);
        while (!q.empty()) {
            Node* current = q.front();
            q.pop();
            // Go through each neighbor of the node
            for (Node* neighbor : current->neighbors) {
                if (cloneMap.find(neighbor) == cloneMap.end()) {
                    // If the neighbor is not cloned yet, clone it
                    cloneMap[neighbor] = new Node(neighbor->val);
                    q.push(neighbor);
                }
                // Attach the cloned neighbor to the cloned node's neighbors list
                cloneMap[current]->neighbors.push_back(cloneMap[neighbor]);
            }
        }
        // The node from cloneMap corresponding to the input node is returned
        return cloneMap[node];
    }
};