The undirected graph allows you to move in both directions of the edge, unlike the directed graph where you can only move in one direction which is specified. One interesting leetcode problem with undirected graphs is the Clone Graph Problem, which we will try to solve here!
What is the Clone Graph Problem?
In the Clone Graph problem, we are given an undirected connected graph. We have to clone this graph such that the new graph is a deep copy of the given graph. Deep Copy creates a new variable that stores the value of the previous variables.
Let’s understand the Clone Graph problem with an example:
Note: All the values of nodes are distinct.
Breath First Search Approach
In the BFS approach using C++, we will traverse the graph levels. We will create a queue that will help us to store the nodes in order of their levels. We will also use the hash map to check what are the neighbouring nodes of each node.
Here’s how we will do it for Clone Graph problem:
- First create two maps, one to store neighboring nodes of each node and the other to store the new node address associated with the given value of the node.
- Now create a queue and store the root node in it. Now call the loop till the size of the queue is greater than 0.
- Create a new node that has a value the same as the front element of the queue. Store the address of this newly created node in the map.
- Now check for all the neighboring elements of this node and store the values of each node in the newly created array.
- Now iterate over all the newly created nodes call their neighbouring elements value and assign the nodes associated with that value to the neighboring nodes of the current node.
- At last return the node with value 1.
The time complexity for the above process is O(m log (m)), where n is the total number of nodes in the graph. As we are doing BFS whose time complexity is O(n) and inserting the value into the map took O(n log(n)) time. So the overall time complexity will be O(n log(n)). The space complexity is O(n) storing the nodes in the map.
Depth First Search Approach
The best way to solve the Clone Graph problem is by going to each node and copying the values of each node into a new node. We will start from the root node and keep on traversing the adjacent nodes till we reach the same elements again. We will use the map to store the visited nodes to check the repeated elements.
In this DFS approach, we will perform the following steps:
- First, create a function DFS that will return the cloned graph. Pass the root of the given graph.
- Now check the base condition, if the root node is NULL return NULL.
- Create a new node and store the root node’s value in this. Also, mark the node value visited in the map.
- Call all the nodes adjacent to the root node and check if they are previously visited or not. If they are previously visited push the node that was created earlier to the neighboring vector of the current root.
- Otherwise, call the DFS function for this node and push the resultant node to the neighbouring vector of the current root.
- Return the head of the new node.
Now, it’s time to implement it.
C++ Code
Here is the C++ solution for Clone Graph problem:
#include<bits/stdc++.h>
using namespace std;
class Node {
public:
int val;
vector<Node*> neighbors;
Node() {
val = 0;
neighbors = vector<Node*>();
}
Node(int x) {
val = x;
neighbors = vector<Node*>();
}
};
bool vis[102];
Node* x[102];
Node* dp(Node* node){
if(node==NULL)return NULL;
Node* head=new Node(node->val);
head->val=node->val;
x[head->val]=head;
vis[node->val]=true;
vector<Node *>v=node->neighbors;
vector<Node*>nw;
for(auto child:v){
if(vis[child->val])nw.push_back(x[child->val]);
else nw.push_back(dp(child));
}
head->neighbors=nw;
return x[head->val]=head;
}
int main(){
Node* root1 = new Node(1);
Node* root2 = new Node(2);
Node* root3 = new Node(3);
Node* root4 = new Node(4);
// graph look like this
// 1 .... 2
// . .
// . .
// 4 .... 3
root1->neighbors.push_back(root2);
root1->neighbors.push_back(root4);
root2->neighbors.push_back(root1);
root2->neighbors.push_back(root3);
root3->neighbors.push_back(root2);
root3->neighbors.push_back(root4);
root4->neighbors.push_back(root1);
root4->neighbors.push_back(root3);
// calling function dp
Node* new_root = dp(root1);
return 0;
}
Java Code
We can also perform the DFS approach with Java:
import java.util.*;
class Node {
int val;
List<Node> neighbors;
Node() {
val = 0;
neighbors = new ArrayList<>();
}
Node(int x) {
val = x;
neighbors = new ArrayList<>();
}
}
class DeepCopyGraph {
static boolean[] vis = new boolean[102];
static Node[] x = new Node[102];
static Node dp(Node node) {
if (node == null) return null;
Node head = new Node(node.val);
head.val = node.val;
x[head.val] = head;
vis[node.val] = true;
List<Node> v = node.neighbors;
List<Node> nw = new ArrayList<>();
for (Node child : v) {
if (vis[child.val]) nw.add(x[child.val]);
else nw.add(dp(child));
}
head.neighbors = nw;
x[head.val] = head;
return x[head.val];
}
public static void main(String[] args) {
Node root1 = new Node(1);
Node root2 = new Node(2);
Node root3 = new Node(3);
Node root4 = new Node(4);
// graph looks like this
// 1 .... 2
// . .
// . .
// 4 .... 3
root1.neighbors.add(root2);
root1.neighbors.add(root4);
root2.neighbors.add(root1);
root2.neighbors.add(root3);
root3.neighbors.add(root2);
root3.neighbors.add(root4);
root4.neighbors.add(root1);
root4.neighbors.add(root3);
// calling function dp
Node new_root = dp(root1);
// Your logic to work with new_root
}
}Python Code
Here is the Python program to clone an undirected graph:
class Node: def __init__(self, x): self.val = x self.neighbors = [] def dp(node, vis, x): if node is None: return None head = Node(node.val) head.val = node.val x[head.val] = head vis[node.val] = True v = node.neighbors nw = [] for child in v: if vis[child.val]: nw.append(x[child.val]) else: nw.append(dp(child, vis, x)) head.neighbors = nw x[head.val] = head return x[head.val] if __name__ == "__main__": vis = [False] * 102 x = [None] * 102 root1 = Node(1) root2 = Node(2) root3 = Node(3) root4 = Node(4) # graph looks like this # 1 .... 2 # . . # . . # 4 .... 3 root1.neighbors.extend([root2, root4]) root2.neighbors.extend([root1, root3]) root3.neighbors.extend([root2, root4]) root4.neighbors.extend([root1, root3]) # calling function dp new_root = dp(root1, vis, x)
The time complexity to solve the Clone Graph problem using Depth-First search is O(n log (N)), where n is the total number of nodes in the graph. As we are doing DFS whose time complexity is O(n) and inserting the value into the map took O(n log(n)) time. So the overall time complexity will be O(n log(n)).
The space complexity is O(n) storing the nodes in the map. A similar problem is to detect cycles in an indirect graph, also to be solved using DFS.
Both the approaches have same time and space complexities:
| Approach | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| BFS Approach | O(N log(N)) | O(N) | Traversing the BFS took O(N) time complexity and storing values in the map took log(N) complexity so the overall complexity will become O(N log(N)). |
| DFS Approach | O(N log(N)) | O(N) | Traversing the DFS took O(N) time complexity, and storing values in the map took log(N) complexity so the overall complexity will become O(N log(N)). |
Conclusion
In this post, we solved the Clone Graph Problem from leetcode. We tried different approaches. One is BFS which does not use any extra stack space as it is an iterative approach, whereas the DFS approach takes extra stack space as it is the recursive approach.
