Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Approach
2.2.
Algorithm
2.3.
DRY Run
2.4.
Implementation in C++
2.5.
Implementation in Java
2.6.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is an undirected graph?
3.2.
What do V and E stand for in a graph?
3.3.
What is the difference between a directed and an undirected graph? 
3.4.
What is the maximum number of edges in the undirected graph of Nodes N? 
3.5.
How do we know the graph is cloned?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Clone of an undirected graph

Author dhananjay
3 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

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. 

introduction image

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

example image

Output

example image

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

  1. Initialize the structure of the node in the graph.
     
  2. Define the nodes of the original node and return the root node.
     
  3. Initialize the vector with each value in the vector as NULL.
     
  4. Check the root node. If the root node is NULL, return NULL.
     
  5. If the adjacent nodes in the root node are empty, return the root node.
     
  6. Call the cloneGraph(rootnode, vector<Node*>) to apply DFS, clone the original graph, and compare the addresses of the original and cloned.
     
  7. Initialize a new Node node* and insert the data from the original node.
     
  8. Print the data and addresses of the original and cloned node.
     
  9. Initialize the index value of data from the original node with the cloned node.
     
  10. 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*>).
       
  11. Repeat until all adjacent nodes are visited.
     
  12. Return the cloned node.

DRY Run

DRY Run
DRY Run image

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.

DRY Run image

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

c++ 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

java code 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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is an undirected graph?

The graph, which is bidirectional in nature, is known as the undirected graph.

What do V and E stand for in a graph?

The V stands for vertices, and E stands for Edges in a graph.

What is the difference between a directed and an undirected graph? 

The directed graph contains ordered pairs of vertices, while the undirected graph contains unordered vertices. In a directed graph, edges represent the direction Of vertices, while edges do not represent the direction of vertices. 

What is the maximum number of edges in the undirected graph of Nodes N? 

Each node can have an edge with every other n-1 node in an undirected graph. Therefore the total number of edges possible is n*(n-1)/2.

How do we know the graph is cloned?

If the nodes and adjacency nodes in the cloned graph are the same as an original graph with different memory addresses, then it is a cloned graph.

Conclusion

In this blog, we have learned how to clone an undirected graph using the Depth-first search approach. We have also implemented the solution to the problem.

To learn more programming problems check out the following links.

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available. Please check out our interview experiences and interview bundle for placement preparations.

Happy Coding!

Previous article
Euler and Hamiltonian Paths
Next article
Clone a Directed Acyclic Graph
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass