Clone a Graph Editorial

Practice Problem Link: Clone a Graph

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given the 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 and a list of its neighbors.

There are n nodes in the graph each with a unique value from 0 to n-1.

class Node {
    public int value;
    public List<Node> neighbors;
}

The given node will have a value of 0. You need to return a copy of this node as a reference to the cloned graph.

Approach

The idea is to perform a traversal of the given graph and for every adjacent node of the current node, if the adjacent node was not visited earlier then make a clone of that node and store it in a hashmap with node value as the key. Also, connect the clone of adjacent and current nodes. If the adjacent node is already visited and its clone is stored in the hashmap then simply connect the clones of the two nodes.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++ (BFS)

/*
This is the Node class definition

class Node {
  public:
    int value = 0;
    vector<Node *> neighbors;
    Node(int val) { value = val; }
};
*/

Node *cloneGraph(Node *node) {
    unordered_map<int, Node*> visitedNodes;
	queue<Node*> queue;
	queue.push(node);
	Node* newRoot = new Node(node->value);
	visitedNodes[node->value] = newRoot;
	while(!queue.empty()) {
		Node* currNode = queue.front();
		queue.pop();
		Node* copyNode = visitedNodes[currNode->value];
		for (int i = 0; i < currNode->neighbors.size(); i++) {
			int key = currNode->neighbors[i]->value;
			if (visitedNodes.find(key) != visitedNodes.end()) {
				copyNode->neighbors.push_back(visitedNodes[key]);
			} else {
				Node* newChild = new Node(key);
				copyNode->neighbors.push_back(newChild);
				visitedNodes[key] = newChild;
				queue.push(currNode->neighbors[i]);
			}
		}
	}
	return newRoot;
}

C++ (DFS)

/*
This is the Node class definition

class Node {
  public:
    int value = 0;
    vector<Node *> neighbors;
    Node(int val) { value = val; }
};
*/
unordered_map<int, Node*> visitedNodes;
Node* cloneGraphUtil(Node *root) {
	Node* copyRoot = new Node(root->value);
	visitedNodes[root->value] = copyRoot;
	for (int i = 0; i < root->neighbors.size(); i++) {
		int key = root->neighbors[i]->value;
		if (visitedNodes.find(key) != visitedNodes.end()) {
			copyRoot->neighbors.push_back(visitedNodes[key]);
		} else {
			Node* copyNode = cloneGraphUtil(root->neighbors[i]);
			copyRoot->neighbors.push_back(copyNode);
		}
	}
	return copyRoot;
}
Node *cloneGraph(Node *node) {
    visitedNodes.clear();
	return cloneGraphUtil(node);
}

Java (BFS)

/* This is the Node class definition
class Node {
public
    int value = 0;
    ArrayList<Node> neighbors = new ArrayList<Node>();
    Node(int val) { value = val; }
};
*/

class Solution {
    Node cloneGraph(Node node) {
        HashMap<Integer, Node> visitedNodes = new HashMap<Integer, Node>();
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(node);
		Node newRoot = new Node(node.value);
		visitedNodes.put(node.value, newRoot);
		while(!queue.isEmpty()) {
			Node currNode = queue.poll();
			Node copyNode = visitedNodes.get(currNode.value);
			for (int i = 0; i < currNode.neighbors.size(); i++) {
				int key = currNode.neighbors.get(i).value;
				if (visitedNodes.containsKey(key)) {
					copyNode.neighbors.add(visitedNodes.get(key));
				} else {
					Node newChild = new Node(key);
					copyNode.neighbors.add(newChild);
					visitedNodes.put(key, newChild);
					queue.add(currNode.neighbors.get(i));
				}
			}
		}
		return newRoot;
    }
}

Java (DFS)

/* This is the Node class definition
class Node {
public
    int value = 0;
    ArrayList<Node> neighbors = new ArrayList<Node>();
    Node(int val) { value = val; }
};
*/

class Solution {
	HashMap<Integer, Node> visitedNodes = new HashMap<Integer, Node>();
	Node cloneGraphUtil(Node root) {
		Node copyRoot = new Node(root.value);
		visitedNodes.put(root.value, copyRoot);
		for (int i = 0; i < root.neighbors.size(); i++) {
			int key = root.neighbors.get(i).value;
			if (visitedNodes.containsKey(key)) {
				copyRoot.neighbors.add(visitedNodes.get(key));
			} else {
				Node copyNode = cloneGraphUtil(root.neighbors.get(i));
				copyRoot.neighbors.add(copyNode);
			}
		}
		return copyRoot;
	}
    Node cloneGraph(Node node) {
        visitedNodes.clear();
		return cloneGraphUtil(node);
    }
}