Clone a graph (Not that easy as it looks)

Dec 18, 2024 • 5 mins read

Problem Overview

In the LeetCode problem "Clone Graph," the task is to create a deep copy of an undirected graph. Each node in the graph contains a unique integer value and a list of its neighbors. The graph is connected and could be cyclical, meaning it could have loops. The main objective is to build a new graph that is an exact replica of the original one, maintaining all the connections among nodes.

Understanding the Problem

Graph cloning involves nodes connected in various ways represented using adjacency lists. Each node knows about its neighboring nodes. The challenge is to ensure that every node is recreated along with its relationships with other nodes. It is similar to making a replica of something, where each component is placed exactly as in the original structure but as a new independent entity.

Example

Consider a simple graph:

1 -- 2
|    |
4 -- 3

This graph can be represented as:

Node 1: [2, 4]
Node 2: [1, 3]
Node 3: [2, 4]
Node 4: [1, 3]

A cloned graph should exactly represent these connections with new nodes having the same relationship.

Key DSA Concepts and Theory

Graphs

Graphs consist of nodes (vertices) connected by edges. They are versatile data structures used to solve real-world problems such as networking, transactions, and navigation.

Node/Vertex: A fundamental part of a graph containing a value or name.
Edge: Connection between two nodes.

Depth-First Search (DFS)

DFS is a traversal method to explore nodes and edges of a graph. It uses a stack (implicitly through recursion) to explore as far as possible along a branch before backing up.

HashMap (Dictionary)

A HashMap or dictionary is used for efficient data retrieval. It stores data in key-value pairs, where each key is unique.

Solution Approach

To solve the problem of graph cloning, we use both DFS and a HashMap to manage cloning states:

Steps

Map Creation: Use a HashMap <Node, Node> to keep track of the original node and its cloned copy.
DFS Traversal & Cloning:
- For each unvisited node, clone the node.
- Recursively clone its neighbors.
- Store the clone in the HashMap.
Return Cloned Node: Upon completing the cloning of neighbors, return the cloned node.

C++ Code

#include <unordered_map>
#include <vector>

// Definition for a Node
class Node {
public:
    int val;
    std::vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = std::vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = std::vector<Node*>();
    }
    Node(int _val, std::vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

class Solution {
private:
    std::unordered_map<Node*, Node*> visited;
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        
        // Check if the node is already visited
        if (visited.find(node) != visited.end()) {
            return visited[node];
        }
        
        // Clone the node
        Node* cloneNode = new Node(node->val);
        visited[node] = cloneNode;
        
        // Clone neighbors
        for (Node* neighbor : node->neighbors) {
            cloneNode->neighbors.push_back(cloneGraph(neighbor));
        }
        
        return cloneNode;
    }
};

Java Code

import java.util.*;

// Definition for a Node
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

class Solution {
    private HashMap<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) return null;

        // Check if the node is already visited
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Clone the node
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);

        // Clone neighbors
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }
}

Time and Space Complexity Analysis

Time Complexity:
- Each node and each edge are traversed once. Thus, the time complexity is O(N + E), where N is the number of nodes, and E is the number of edges.
Space Complexity:
- The space complexity is O(N). This is primarily due to the space used by the HashMap for storing nodes and their clones during the depth-first search.

Common Mistakes to Avoid

Failing to account for cycles which can lead to infinite loops during traversal.
Not appropriately checking for null inputs.
Omitting to use a HashMap, which results in duplicating nodes or incorrect references.

Additional Resources and References

Books on Graph Theory and applications: "Algorithms, Part II" from Coursera, "Introduction to Graph Theory" by Richard J. Trudeau.
Articles on DFS and BFS: GeeksforGeeks, and TopCoder tutorials.
Visualization tools for graphs: Desmos, Graphviz.

This comprehensive overview of the "Clone Graph" problem should equip you well to understand and solve similar graph-related challenges.