Introduction
A graph is a data structure containing vertices and edges. Vertices are nodes containing data, and edges are connected lines between vertices. The graph has many real-life applications, making it a common topic to ask during interviews. So it will be better for you to understand the fundamentals of graphs.
In this blog, we will implement a famous problem on various coding platforms which might run into during your coding interviews. Let's discuss the problem statement.
Problem Statement
We will be given an undirected connected graph, and our task is to clone that graph. In an undirected graph, the edges will be bidirectional, meaning you can traverse in both directions of two connected nodes.
You will have ‘N’ nodes with an adjacency list of each node. The adjacency list will tell us the connection between nodes. Our task is to make a copy of the original nodes.
Example
Input
Output
We can observe that both graphs have the same nodes with the same adjacent nodes. We have cloned the graph.
Ensure you are not returning the addresses of the original graph as output. Our graphs will be differentiated on the bases of the addresses of nodes.
Approach
Since we need to traverse all the nodes and adjacent nodes in the original graph to make a copy, we can be sure of the recursive approach. We can use the DFS Algorithm approach to traverse the nodes and make a clone.
We will create a new node first and insert the data from the current node from the original graph. We will use a vector of type node* that will be initialized with null values. After inserting the data in the clone graph node, we will add the clone node address to the data index from the current node.
The initialized vector will save us from traversing the nodes already traversed and added to the clone graph. Since it is a bidirectional graph, you must visit the node added in the cloned graph because it will be in an adjacency list of other nodes.
If the node is already visited, we add it as an adjacent node of the current node, not as the vertices in the cloned graph.
After adding all the nodes and adjacency nodes in the cloned graph, we will return the root node and print the original and cloned graphs. We will compare the addresses of the original and cloned nodes because it will show us the whether we have cloned the graph.
Algorithm
-
Initialize the structure of the node in the graph.
-
Define the nodes of the original node and return the root node.
-
Initialize the vector with each value in the vector as NULL.
-
Check the root node. If the root node is NULL, return NULL.
-
If the adjacent nodes in the root node are empty, return the root node.
-
Call the cloneGraph(rootnode, vector<Node*>) to apply DFS, clone the original graph, and compare the addresses of the original and cloned.
-
Initialize a new Node node* and insert the data from the original node.
-
Print the data and addresses of the original and cloned node.
-
Initialize the index value of data from the original node with the cloned node.
-
Check if the cloned graph's current node's adjacency node is visited.
-
If not visited, add them as vertices in the cloned graph.
-
Else recursively call cloneGraph(node, vector<Node*>).
-
If not visited, add them as vertices in the cloned graph.
-
Repeat until all adjacent nodes are visited.
- Return the cloned node.
DRY Run
Now at current node 2, we can observe that we have visited both nodes 1 and 4. Now we will just return to the starting node in our clone graph to mark the last node 2 with starting node 1 as adjacency nodes and complete the cloning of our graph.
Implementation in C++
#include<bits/stdc++.h>
using namespace std;
// Intializing the structure for node.
struct Node{
int data;
vector<Node*> adjacentnodes;
};
// Function to clone the orginal graph and print both.
Node* cloningGraph(Node* curr,vector<Node*> &checked)
{
vector<Node*> othernodes;
// Intializing the clone node
Node* clone = new Node();
clone->data = curr->data;
// Marking the Cloned node.
checked[curr->data] = clone;
// Iterating on adjacent nodes.
// Adding unvisited nodes in the clone graph.
for(auto ele: curr->adjacentnodes)
{
if(checked[ele->data]!=NULL)
{
othernodes.push_back(checked[ele->data]);
}
else
othernodes.push_back(cloningGraph(ele,checked));
}
clone->adjacentnodes = othernodes;
// Returning the clone node to calling function.
return clone;
}
// Function to initialize the cloned graph.
Node *clone(Node *rootnode){
vector<Node*>checked(10,NULL);
if(rootnode==NULL){
return NULL;
}
if(rootnode->adjacentnodes.empty()){
Node *clone = new Node();
clone->data = rootnode->data;
return clone;
}
return cloningGraph(rootnode,checked);
}
// Function to create the graph.
Node *createGraph(){
Node *firstnode = new Node();
firstnode->data = 1;
Node *secondnode = new Node();
secondnode->data = 3;
Node *thirdnode = new Node();
thirdnode->data = 4;
Node *fourthnode = new Node();
fourthnode->data = 2;
vector<Node*> temp;
temp.push_back(secondnode);
temp.push_back(fourthnode);
firstnode->adjacentnodes = temp;
temp.clear();
temp.push_back(firstnode);
temp.push_back(thirdnode);
secondnode->adjacentnodes = temp;
temp.clear();
temp.push_back(secondnode);
temp.push_back(fourthnode);
thirdnode->adjacentnodes = temp;
temp.clear();
temp.push_back(firstnode);
temp.push_back(thirdnode);
fourthnode->adjacentnodes = temp;
temp.clear();
return firstnode;
}
// Function to print the graph.
void printGraph(Node *root)
{
map<Node*, bool> mark;
queue<Node*> que;
que.push(root);
mark[root] = true;
// Printing until queue is empty.
while (!que.empty())
{
Node *temp = que.front();
cout << "Node" << temp->data << "->";
que.pop();
for (auto node:temp->adjacentnodes)
{
cout<<node->data<<" ";
if (!mark[node])
{
mark[node] = true;
que.push(node);
}
}
cout<<endl;
}
cout << endl;
}
// Driver Function.
int main(){
vector<bool> mark;
// Original Graph
Node *rootnode = createGraph();
cout<<"Graph Nodes with adjacent Nodes"<<"\n \n";
cout<<"Original Graph"<<endl;
printGraph(rootnode);
// Cloned Graph
Node *result = clone(rootnode);
cout<<"Cloned Graph"<<endl;
printGraph(result);
return 0;
}
Output
Implementation in Java
import java.util.*;
// Intializing the structure for node.
class Node{
int data;
Vector<Node> adjacentnodes;
public Node(int data){
this.data = data;
adjacentnodes = new Vector<Node>();
}
}
class undirectedGraph{
// Function to clone the orginal graph and print both.
public Node cloningGraph(Node root, Node[] checked){
// Vector to store adjacent nodes.
Vector<Node> othernodes = new Vector<>();
// Initializing the clone node
Node clone = new Node(root.data);
// Marking the Cloned node
checked[root.data] = clone;
// Iterating on adjacent nodes.
// Adding unvisited nodes in the clone graph.
for(Node ele:root.adjacentnodes){
if(checked[ele.data]!=null){
othernodes.add(checked[ele.data]);
}
else{
othernodes.add(cloningGraph(ele,checked));
}
}
// Adding adjacent nodes in current node in clone graph.
clone.adjacentnodes = othernodes;
// Returning the cloned node to calling function.
return clone;
}
// Function to initialize the cloned graph.
public Node clone(Node root){
Node[] checked = new Node[10];
Arrays.fill(checked,null);
if(root==null){
return null;
}
if(root.adjacentnodes.isEmpty()){
Node clone = new Node(root.data);
return clone;
}
return cloningGraph(root,checked);
}
// Function to create the graph.
public Node createGraph(){
Node firstnode = new Node(1);
Node secondnode = new Node(3);
Node thirdnode = new Node(4);
Node fourthnode = new Node(2);
Vector<Node> temp = new Vector<Node>();
temp.add(secondnode);
temp.add(fourthnode);
firstnode.adjacentnodes = temp;
temp = new Vector<Node>();
temp.add(firstnode);
temp.add(thirdnode);
secondnode.adjacentnodes = temp;
temp = new Vector<Node>();
temp.add(secondnode);
temp.add(fourthnode);
thirdnode.adjacentnodes = temp;
temp = new Vector<Node>();
temp.add(firstnode);
temp.add(thirdnode);
fourthnode.adjacentnodes = temp;
temp = new Vector<Node>();
return firstnode;
}
// Function to print the graph.
public void printGraph(Node root){
HashMap<Node,Boolean> mark = new HashMap<Node,Boolean>();
Queue<Node> que = new LinkedList<Node>();
que.add(root);
mark.put(root,true);
// Printing until queue is empty.
while(!que.isEmpty()){
Node temp = que.poll();
System.out.print("Node" + temp.data + "->");
if(temp.adjacentnodes!=null){
for(Node node:temp.adjacentnodes){
System.out.print(node.data + " ");
if(mark.get(node)==null){
que.add(node);
mark.put(node,true);
}
}
System.out.println();
}
}
}
}
// Main class.
public class Main{
public static void main(String[] args){
undirectedGraph obj = new undirectedGraph();
Node rootnode = obj.createGraph();
System.out.println("Graph Nodes with adjacent Nodes \n");
System.out.println("Original Graph");
obj.printGraph(rootnode);
System.out.println("\nCloned Graph");
Node result = obj.clone(rootnode);
obj.printGraph(result);
}
}
Output
Complexity Analysis
The time complexity for the above approach will be O(N), where ‘N’ equals the Vertices + Edges of the original graph. Since we have to traverse n number of nodes in the original graph to clone it in a new graph, the time complexity in the worst case will be O(N).
The space complexity for the above approach will be O(N), where ‘N’ is equal to the Vertices + Edges of the original graph. We have to traverse and store each node and edge. That's why the space complexity for the above approach will be O(N).
Check out this problem - Connect Nodes At Same Level
117+ registered 