Clone Graph
Program for Clone Graph in an Undirected Graph
You are given a node from a connected, undirected graph. Your task is to create an exact copy (a deep copy) of the entire graph.
Each node in the graph has two properties:
- An integer value (val), which represents the node’s label.
- A list of neighboring nodes (neighbors), which contains the nodes directly connected to it.
The graph is represented using an adjacency list, which is a way to describe the connections between nodes. The adjacency list maps each node to a list of its neighbors.
For simplicity:
- The node values range from 1 to n, where n is the total number of nodes.
- The node’s position in the adjacency list matches its value (1-indexed). For example, the first position in the adjacency list corresponds to the node with value 1.
The input node will always be the first node in the graph, and its value will be 1.
Example 1:
Output: [[2],[1,3],[2]]
Explanation:
There are 3 nodes in the graph-
- Node 1: val = 1 and neighbors = [2].
- Node 2: val = 2 and neighbors = [1, 3].
- Node 3: val = 3 and neighbors = [2].
Output: [ ]
Explanation: The graph is empty.
Constraints :
- 0 <= The number of nodes in the graph <= 100.
- 1 <= Node.val <= 100
- There are no duplicate edges and no self-loops in the graph.
Solution for Clone Graph in an Undirected Graph
Recommendation for Time and Space Complexity – Aim for O(V + E) time and O(E) space, where V is the number of vertices and E is the number of edges.
Hints for solving problems
Hint 1
To clone the graph, you must copy all nodes and their connections. Use a recursive approach to copy each node and its neighbors. A hash map can help store the original nodes and their cloned references.
Hint 2
Use Depth First Search (DFS) to traverse and clone the graph. Start at the given node, create its clone, and recursively clone its neighbors. Add the cloned neighbors to the current node’s neighbors list.
Hint 3
Stop the recursion when you encounter a node that is already cloned (tracked in the hash map). This ensures you don’t visit the same node twice. Return the clone of the input node after the process.
There are mainly 2 approach to solve this problem-
- Depth First Search Method
- Breadth First Search Method
1. Depth First Method
In the DFS method, you use recursion to traverse the graph starting from the given node. At each node, you create its clone, recursively clone its neighbors, and add the cloned neighbors to the current node’s neighbors list. A hash map keeps track of visited nodes to avoid duplicate cloning.
- Time complexity: O(V + E)
- Space complexity: O(V)
where V is the number of vertices and E is the number of edges.
Code
/*
// 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) {
map<Node*, Node*> oldToNew;
return dfs(node, oldToNew);
}
Node* dfs(Node* node, map<Node*, Node*>& oldToNew) {
if (node == nullptr) {
return nullptr;
}
if (oldToNew.count(node)) {
return oldToNew[node];
}
Node* copy = new Node(node->val);
oldToNew[node] = copy;
for (Node* nei : node->neighbors) {
copy->neighbors.push_back(dfs(nei, oldToNew));
}
return copy;
}
};
/*
Definition for a Node.
class Node {
public int val;
public List neighbors;
public Node() {
val = 0;
neighbors = new ArrayList();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList();
}
public Node(int _val, ArrayList _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
public class Solution {
public Node cloneGraph(Node node) {
Map<Node, Node> oldToNew = new HashMap<>();
return dfs(node, oldToNew);
}
private Node dfs(Node node, Map<Node, Node> oldToNew) {
if (node == null) {
return null;
}
if (oldToNew.containsKey(node)) {
return oldToNew.get(node);
}
Node copy = new Node(node.val);
oldToNew.put(node, copy);
for (Node nei : node.neighbors) {
copy.neighbors.add(dfs(nei, oldToNew));
}
return copy;
}
}
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
oldToNew = {}
def dfs(node):
if node in oldToNew:
return oldToNew[node]
copy = Node(node.val)
oldToNew[node] = copy
for nei in node.neighbors:
copy.neighbors.append(dfs(nei))
return copy
return dfs(node) if node else None
/**
* // Definition for a Node.
* class Node {
* constructor(val = 0, neighbors = []) {
* this.val = val;
* this.neighbors = neighbors;
* }
* }
*/
class Solution {
/**
* @param {Node} node
* @return {Node}
*/
cloneGraph(node) {
const oldToNew = new Map();
return this.dfs(node, oldToNew);
}
/**
* @param {Node} node
* @param {Map} oldToNew
* @return {Node}
*/
dfs(node, oldToNew) {
if (node === null) {
return null;
}
if (oldToNew.has(node)) {
return oldToNew.get(node);
}
const copy = new Node(node.val);
oldToNew.set(node, copy);
for (const nei of node.neighbors) {
copy.neighbors.push(this.dfs(nei, oldToNew));
}
return copy;
}
}
2. Breadth First Search Method
In the BFS method, you use a queue to traverse the graph level by level. Start by cloning the given node and pushing it into the queue. For each node in the queue, clone its neighbors, add the cloned neighbors to the node’s list, and enqueue unvisited neighbors. A hash map is used to track visited nodes.
- Time complexity: O(V + E)
- Space complexity: O(V)
where V is the number of vertices and E is the number of edges.
Code
/*
// 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) return nullptr;
unordered_map<N
ode*, Node*> oldToNew;
queue<Node*> q;
oldToNew[node] = new Node(node->val);
q.push(node);
while (!q.empty()) {
Node* cur = q.front();
q.pop();
for (Node* nei : cur->neighbors) {
if (oldToNew.find(nei) == oldToNew.end()) {
oldToNew[nei] = new Node(nei->val);
q.push(nei);
}
oldToNew[cur]->neighbors.push_back(oldToNew[nei]);
}
}
return oldToNew[node];
}
};
/*
Definition for a Node.
class Node {
public int val;
public List neighbors;
public Node() {
val = 0;
neighbors = new ArrayList();
}
public Node(int _val) {
val = _val;
neighbors = new ArrayList();
}
public Node(int _val, ArrayList _neighbors) {
val = _val;
neighbors = _neighbors;
}
}
*/
public class Solution {
public Node cloneGraph(Node node) {
if (node == null) return null;
Map<Node, Node> oldToNew = new HashMap<>();
Queue q = new LinkedList<>();
oldToNew.put(node, new Node(node.val));
q.add(node);
while (!q.isEmpty()) {
Node cur = q.poll();
for (Node nei : cur.neighbors) {
if (!oldToNew.containsKey(nei)) {
oldToNew.put(nei, new Node(nei.val));
q.add(nei);
}
oldToNew.get(cur).neighbors.add(oldToNew.get(nei));
}
}
return oldToNew.get(node);
}
}
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return None
oldToNew = {}
oldToNew[node] = Node(node.val)
q = deque([node])
while q:
cur = q.popleft()
for nei in cur.neighbors:
if nei not in oldToNew:
oldToNew[nei] = Node(nei.val)
q.append(nei)
oldToNew[cur].neighbors.append(oldToNew[nei])
return oldToNew[node]
/**
* // Definition for a Node.
* class Node {
* constructor(val = 0, neighbors = []) {
* this.val = val;
* this.neighbors = neighbors;
* }
* }
*/
class Solution {
/**
* @param {Node} node
* @return {Node}
*/
cloneGraph(node) {
if (!node) return null;
const oldToNew = new Map();
const q = new Queue();
oldToNew.set(node, new Node(node.val));
q.push(node);
while (!q.isEmpty()) {
const cur = q.pop();
for (const nei of cur.neighbors) {
if (!oldToNew.has(nei)) {
oldToNew.set(nei, new Node(nei.val));
q.push(nei);
}
oldToNew.get(cur).neighbors.push(oldToNew.get(nei));
}
}
return oldToNew.get(node);
}
}
