C++: Clone Graph

Thought Process

To clone a graph, we need to create a deep copy of all its nodes and their connections. We use a Breadth-First Search (BFS) approach to traverse the original graph. Also, we maintain a hash map to store the mapping between the original nodes and their corresponding cloned nodes. This ensures that we do not create duplicate copies of the same node.

We start by cloning the root node and adding it to the queue. For each node, we iterate through its neighbors. If a neighbor hasn't been cloned yet, we create a new clone and add it to the hash map and the queue. Further, we add the cloned neighbor to the adjacency list of the current cloned node. This process continues until the queue is empty. 

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

class Solution {
public:
    Node* cloneGraph(Node* node) {
        
        if(node == NULL)
            return NULL;

        // Original to Copy
        unordered_map<Node*,Node*> umap;
        umap[node] = new Node(node->val);

        // Applying BFS Traversal
        queue<Node*> qu;
        qu.push(node);

        while(!qu.empty()){

            Node* nod = qu.front(); qu.pop();
            // Iterate Neighbor element of nod
            for(int i=0;i<nod->neighbors.size();i++){

                Node* n1 = nod->neighbors[i];
                // If neighbor elements doesn't exist in map
                if(!umap.count(n1)){
                    umap[n1] = new Node(n1->val);
                    qu.push(n1);
                }
                // Put the copy of n1 node to the adjacency list.
                // Add the neighbor in our cloned graph.
                umap[nod]->neighbors.push_back(umap[n1]);
            }
        }
        return umap[node];
    }
};

Code Complexity

Time Complexity: O(V + E)

The algorithm traverses each node (V) and each edge ( E) exactly once, making it linear in terms of the number of nodes and edges.

Space Complexity: O(V)

The algorithm uses a hash map to store all the nodes, which requires space proportional to the number of nodes (V).

Code copied!