Clone Graph

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 (int) and a list (List[Node]) of its neighbors.

 

Test case format:

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list.

An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Shell

The gist of the problem

Ok… a lot of information up front… but what’s really going on here? You’re first instinct is probably to consider how to traverse a graph in an optimal fashion, but the problem really isn’t about traversing a graph optimally, it’s about copying the graph. But let’s back up even further. What is a graph? What’s going on here? And why would we want to copy it?

If you aren’t familiar with graph data structures, you should familiarize yourself with them. If you are, then the question becomes how do we think about graph data structures in the lens of this problem.

From a visual perspective, roughly we have

The challenge of copying each node and each neighbor list with a reference to only a single node. So straight away you can see we’ll need two things

  1. A means of keeping track of what nodes we’ve visited and what we haven’t

  2. A traversal process for navigating the graph

The way we accomplish 1 - 2 depends on our strategy, so let’s figure out what that is. The challenge of creating a deep copy makes things interesting. We can’t really just visit each node and deep copy it’s neighbor list, since those nodes don’t exist yet. We need some way of visiting each node in the graph and copying it’s neighbors when… they don’t exist yet.

The first impulse that comes to mind is to use recursion, recurse on each neighbor we haven’t yet visited, or simply add to our neighbor list a neighbor if we’ve already visited it…

This works, the time and space complexity is O(m) where m is the number of nodes in the graph. 

class Node {
    public int val;
    public List<Node> neighbors;
}
/*
// 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) {
        
    }
};
class Solution {
public:
    Node* cloneGraph(Node* node) {
        unordered_map<int, Node*> new_nodes = unordered_map<int, Node*>();
        return cloneGraphInternal(node, &new_nodes);
    }
    Node* cloneGraphInternal(Node* node, unordered_map<int, Node*>* newNodes) {
        if (node == NULL) {
            return NULL;
        }
        Node* copy = new Node(node->val);
        newNodes->insert({node->val, copy});
        for (Node* n : node->neighbors) {
            if (auto search = newNodes->find(n->val); search != newNodes->end()) {
                copy->neighbors.emplace_back((*newNodes)[n->val]);
            }
            else
            {
                copy->neighbors.emplace_back(cloneGraphInternal(n, newNodes));
            }
        }
        return copy;
    }
};