Clone an Undirected Graph

Last Updated : 02 Mar, 2023

Cloning of a LinkedList and a Binary Tree with random pointers has already been discussed. The idea behind cloning a graph is pretty much similar.

The idea is to do a BFS traversal of the graph and while visiting a node make a clone node of it (a copy of original node). If a node is encountered which is already visited then it already has a clone node.

How to keep track of the visited/cloned nodes? A HashMap/Map is required in order to maintain all the nodes which have already been created. Key stores: Reference/Address of original Node Value stores: Reference/Address of cloned Node A copy of all the graph nodes has been made,

how to connect clone nodes? While visiting the neighboring vertices of a node u get the corresponding cloned node for u , let’s call that cloneNodeU , now visit all the neighboring nodes for u and for each neighbor find the corresponding clone node(if not found create one) and then push into the neighboring vector of cloneNodeU node.

How to verify if the cloned graph is a correct? Do a BFS traversal before and after the cloning of graph. In BFS traversal display the value of a node along with its address/reference. Compare the order in which nodes are displayed, if the values are same but the address/reference is different for both the traversals then the cloned graph is correct.

Implementation:

C++

// A C++ program to Clone an Undirected Graph
#include<bits/stdc++.h>
using namespace std;
 
struct GraphNode
{
    int val;
 
    //A neighbour vector which contains addresses to
    //all the neighbours of a GraphNode
    vector<GraphNode*> neighbours;
};
 
// A function which clones a Graph and
// returns the address to the cloned
// src node
GraphNode *cloneGraph(GraphNode *src)
{
    //A Map to keep track of all the
    //nodes which have already been created
    map<GraphNode*, GraphNode*> m;
    queue<GraphNode*> q;
 
    // Enqueue src node
    q.push(src);
    GraphNode *node;
 
    // Make a clone Node
    node = new GraphNode();
    node->val = src->val;
 
    // Put the clone node into the Map
    m[src] = node;
    while (!q.empty())
    {
        //Get the front node from the queue
        //and then visit all its neighbours
        GraphNode *u = q.front();
        q.pop();
        vector<GraphNode *> v = u->neighbours;
        int n = v.size();
        for (int i = 0; i < n; i++)
        {
            // Check if this node has already been created
            if (m[v[i]] == NULL)
            {
                // If not then create a new Node and
                // put into the HashMap
                node = new GraphNode();
                node->val = v[i]->val;
                m[v[i]] = node;
                q.push(v[i]);
            }
 
            // add these neighbours to the cloned graph node
            m[u]->neighbours.push_back(m[v[i]]);
        }
    }
 
    // Return the address of cloned src Node
    return m[src];
}
 
// Build the desired graph
GraphNode *buildGraph()
{
    /*
        Note : All the edges are Undirected
        Given Graph:
        1--2
        | |
        4--3
    */
    GraphNode *node1 = new GraphNode();
    node1->val = 1;
    GraphNode *node2 = new GraphNode();
    node2->val = 2;
    GraphNode *node3 = new GraphNode();
    node3->val = 3;
    GraphNode *node4 = new GraphNode();
    node4->val = 4;
    vector<GraphNode *> v;
    v.push_back(node2);
    v.push_back(node4);
    node1->neighbours = v;
    v.clear();
    v.push_back(node1);
    v.push_back(node3);
    node2->neighbours = v;
    v.clear();
    v.push_back(node2);
    v.push_back(node4);
    node3->neighbours = v;
    v.clear();
    v.push_back(node3);
    v.push_back(node1);
    node4->neighbours = v;
    return node1;
}
 
// A simple bfs traversal of a graph to
// check for proper cloning of the graph
void bfs(GraphNode *src)
{
    map<GraphNode*, bool> visit;
    queue<GraphNode*> q;
    q.push(src);
    visit[src] = true;
    while (!q.empty())
    {
        GraphNode *u = q.front();
        cout << "Value of Node " << u->val << "\n";
        cout << "Address of Node " <<u << "\n";
        q.pop();
        vector<GraphNode *> v = u->neighbours;
        int n = v.size();
        for (int i = 0; i < n; i++)
        {
            if (!visit[v[i]])
            {
                visit[v[i]] = true;
                q.push(v[i]);
            }
        }
    }
    cout << endl;
}
 
// Driver program to test above function
int main()
{
    GraphNode *src = buildGraph();
    cout << "BFS Traversal before cloning\n";
    bfs(src);
    GraphNode *newsrc = cloneGraph(src);
    cout << "BFS Traversal after cloning\n";
    bfs(newsrc);
    return 0;
}

Java

// Java program to Clone an Undirected Graph
import java.util.*;
 
// GraphNode class represents each
// Node of the Graph
class GraphNode
{
    int val;
 
    // A neighbour Vector which contains references to
    // all the neighbours of a GraphNode
    Vector<GraphNode> neighbours;
    public GraphNode(int val)
    {
        this.val = val;
        neighbours = new Vector<GraphNode>();
    }
}
 
class Graph
{
    // A method which clones the graph and
    // returns the reference of new cloned source node
    public GraphNode cloneGraph(GraphNode source)
    {
        Queue<GraphNode> q = new LinkedList<GraphNode>();
        q.add(source);
 
        // An HashMap to keep track of all the
        // nodes which have already been created
        HashMap<GraphNode,GraphNode> hm =
                        new HashMap<GraphNode,GraphNode>();
 
        //Put the node into the HashMap
        hm.put(source,new GraphNode(source.val));
 
        while (!q.isEmpty())
        {
            // Get the front node from the queue
            // and then visit all its neighbours
            GraphNode u = q.poll();
 
            // Get corresponding Cloned Graph Node
            GraphNode cloneNodeU = hm.get(u);
            if (u.neighbours != null)
            {
                Vector<GraphNode> v = u.neighbours;
                for (GraphNode graphNode : v)
                {
                    // Get the corresponding cloned node
                    // If the node is not cloned then we will
                    // simply get a null
                    GraphNode cloneNodeG = hm.get(graphNode);
 
                    // Check if this node has already been created
                    if (cloneNodeG == null)
                    {
                        q.add(graphNode);
 
                        // If not then create a new Node and
                        // put into the HashMap
                        cloneNodeG = new GraphNode(graphNode.val);
                        hm.put(graphNode,cloneNodeG);
                    }
 
                    // add the 'cloneNodeG' to neighbour
                    // vector of the cloneNodeG
                    cloneNodeU.neighbours.add(cloneNodeG);
                }
            }
        }
 
        // Return the reference of cloned source Node
        return hm.get(source);
    }
 
    // Build the desired graph
    public GraphNode buildGraph()
    {
        /*
            Note : All the edges are Undirected
            Given Graph:
            1--2
            |  |
            4--3
        */
        GraphNode node1 = new GraphNode(1);
        GraphNode node2 = new GraphNode(2);
        GraphNode node3 = new GraphNode(3);
        GraphNode node4 = new GraphNode(4);
        Vector<GraphNode> v = new Vector<GraphNode>();
        v.add(node2);
        v.add(node4);
        node1.neighbours = v;
        v = new Vector<GraphNode>();
        v.add(node1);
        v.add(node3);
        node2.neighbours = v;
        v = new Vector<GraphNode>();
        v.add(node2);
        v.add(node4);
        node3.neighbours = v;
        v = new Vector<GraphNode>();
        v.add(node3);
        v.add(node1);
        node4.neighbours = v;
        return node1;
    }
 
    // BFS traversal of a graph to
    // check if the cloned graph is correct
    public void bfs(GraphNode source)
    {
        Queue<GraphNode> q = new LinkedList<GraphNode>();
        q.add(source);
        HashMap<GraphNode,Boolean> visit =
                          new HashMap<GraphNode,Boolean>();
        visit.put(source,true);
        while (!q.isEmpty())
        {
            GraphNode u = q.poll();
            System.out.println("Value of Node " + u.val);
            System.out.println("Address of Node " + u);
            if (u.neighbours != null)
            {
                Vector<GraphNode> v = u.neighbours;
                for (GraphNode g : v)
                {
                    if (visit.get(g) == null)
                    {
                        q.add(g);
                        visit.put(g,true);
                    }
                }
            }
        }
        System.out.println();
    }
}
 
// Driver code
class Main
{
    public static void main(String args[])
    {
        Graph graph = new Graph();
        GraphNode source = graph.buildGraph();
        System.out.println("BFS traversal of a graph before cloning");
        graph.bfs(source);
        GraphNode newSource = graph.cloneGraph(source);
        System.out.println("BFS traversal of a graph after cloning");
        graph.bfs(newSource);
    }
}

Python3

from collections import deque
 
class GraphNode:
    def __init__(self, val=0, neighbors=[]):
        self.val = val
        self.neighbors = neighbors
 
def cloneGraph(src: GraphNode) -> GraphNode:
    # A Map to keep track of all the
    # nodes which have already been created
    m = {}
    q = deque()
 
    # Enqueue src node
    q.append(src)
    node = None
 
    # Make a clone Node
    node = GraphNode()
    node.val = src.val
 
    # Put the clone node into the Map
    m[src] = node
    while q:
        # Get the front node from the queue
        # and then visit all its neighbors
        u = q.popleft()
        v = u.neighbors
        for neighbor in v:
            # Check if this node has already been created
            if neighbor not in m:
                # If not then create a new Node and
                # put into the HashMap
                node = GraphNode()
                node.val = neighbor.val
                m[neighbor] = node
                q.append(neighbor)
 
            # Add these neighbors to the cloned graph node
            m[u].neighbors.append(m[neighbor])
 
    # Return the address of cloned src Node
    return m[src]
 
# Build the desired graph
def buildGraph() -> GraphNode:
    """
    Given Graph:
    1--2
    | |
    4--3
    """
    node1 = GraphNode(1)
    node2 = GraphNode(2)
    node3 = GraphNode(3)
    node4 = GraphNode(4)
    node1.neighbors = [node2, node4]
    node2.neighbors = [node1, node3]
    node3.neighbors = [node2, node4]
    node4.neighbors = [node3, node1]
    return node1
 
# A simple bfs traversal of a graph to
# check for proper cloning of the graph
def bfs(src: GraphNode):
    visit = {}
    q = deque()
    q.append(src)
    visit[src] = True
    while q:
        u = q.popleft()
        print(f"Value of Node {u.val}")
        print(f"Address of Node {u}")
        v = u.neighbors
        for neighbor in v:
            if neighbor not in visit:
                visit[neighbor] = True
                q.append(neighbor)
 
if __name__ == "__main__":
    src = buildGraph()
    print("BFS Traversal before cloning")
    bfs(src)
    clone = cloneGraph(src)
    print("\nBFS Traversal after cloning")
    bfs(clone)
 
    # This code is contributed by vikramshirsath177

Javascript

// A Javascript program to Clone an Undirected Graph
 
// program to implement queue data structure
class Queue {
  constructor() {
    this.items = [];
  }
 
  // add element to the queue
  push(element) {
    return this.items.push(element);
  }
 
  // remove element from the queue
  pop() {
    if (this.items.length > 0) {
      return this.items.shift();
    }
  }
 
  // view the front element
  front() {
    return this.items[0];
  }
 
  // check if the queue is empty
  empty() {
    return this.items.length == 0;
  }
 
  // the size of the queue
  size() {
    return this.items.length;
  }
 
  // empty the queue
  clear() {
    this.items = [];
  }
}
class GraphNode {
  constructor() {
    this.val;
    //A neighbour array which contains addresses to
    //all the neighbours of a GraphNode
    this.neighbours = new Array();
  }
}
class Graph {
  // A function which clones a Graph and
  // returns the address to the cloned
  // src node
  cloneGraph(src) {
    //A Map to keep track of all the
    //nodes which have already been created
    let m = new Map();
    let q = new Queue();
 
    // Enqueue src node
    q.push(src);
    let node;
 
    // Make a clone Node
    node = new GraphNode();
    node.val = src.val;
 
    // Put the clone node into the Map
    m.set(src, node);
    while (!q.empty()) {
      //Get the front node from the queue
      //and then visit all its neighbours
      let u = q.front();
      q.pop();
      let v = u.neighbours;
      let n = v.length;
      for (let i = 0; i < n; i++) {
        // Check if this node has already been created
        if (m.get(v[i]) == null) {
          // If not then create a new Node and
          // put into the Map
          node = new GraphNode();
          node.val = v[i].val;
          m.set(v[i], node);
          q.push(v[i]);
        }
 
        // add these neighbours to the cloned graph node
        m.get(u).neighbours.push(m.get(v[i]));
      }
    }
 
    // Return the address of cloned src Node
    return m.get(src);
  }
 
  // Build the desired graph
  buildGraph() {
    /*
          Note : All the edges are Undirected
          Given Graph:
          1--2
          | |
          4--3
      */
    let node1 = new GraphNode();
    node1.val = 1;
    let node2 = new GraphNode();
    node2.val = 2;
    let node3 = new GraphNode();
    node3.val = 3;
    let node4 = new GraphNode();
    node4.val = 4;
    let v = new Array();
    v.push(node2);
    v.push(node4);
    node1.neighbours = v;
    v = [];
    v.push(node1);
    v.push(node3);
    node2.neighbours = v;
    v = [];
    v.push(node2);
    v.push(node4);
    node3.neighbours = v;
    v = [];
    v.push(node3);
    v.push(node1);
    node4.neighbours = v;
    return node1;
  }
 
  // A simple bfs traversal of a graph to
  // check for proper cloning of the graph
  bfs(src) {
    let visit = new Map();
    let q = new Queue();
    q.push(src);
    visit.set(src, true);
    while (!q.empty()) {
      let u = q.front();
      console.log("Value of Node " + u.val);
      console.log("Address of Node " + u);
      q.pop();
      let v = u.neighbours;
      let n = v.length;
      for (let i = 0; i < n; i++) {
        if (visit.get(v[i]) === undefined) {
          visit.set(v[i], true);
          q.push(v[i]);
        }
      }
    }
    console.log("        ");
  }
}
 
// Driver program to test above function
let graph = new Graph();
let src = graph.buildGraph();
console.log("BFS Traversal before cloning");
graph.bfs(src);
let newsrc = graph.cloneGraph(src);
console.log("BFS Traversal after cloning");
graph.bfs(newsrc);
 
// This code is contributed by satwiksuman.

C#

// A C# program to Clone an Undirected Graph
using System;
using System.Collections.Generic;
using System.Linq;
 
class GraphNode
{
public int val;
public List<GraphNode> neighbors;
public GraphNode(int val = 0, List<GraphNode> neighbors = null)
{
    this.val = val;
    this.neighbors = neighbors ?? new List<GraphNode>();
}
}
 
class Program
{
static GraphNode CloneGraph(GraphNode src)
{
// A Dictionary to keep track of all the
// nodes which have already been created
Dictionary<GraphNode, GraphNode> m = new Dictionary<GraphNode, GraphNode>();
Queue<GraphNode> q = new Queue<GraphNode>();
    // Enqueue src node
    q.Enqueue(src);
    GraphNode node = null;
 
    // Make a clone Node
    node = new GraphNode();
    node.val = src.val;
 
    // Put the clone node into the Dictionary
    m[src] = node;
    while (q.Count > 0)
    {
        // Get the front node from the queue
        // and then visit all its neighbors
        GraphNode u = q.Dequeue();
        List<GraphNode> v = u.neighbors;
        foreach (GraphNode neighbor in v)
        {
            // Check if this node has already been created
            if (!m.ContainsKey(neighbor))
            {
                // If not then create a new Node and
                // put into the Dictionary
                node = new GraphNode();
                node.val = neighbor.val;
                m[neighbor] = node;
                q.Enqueue(neighbor);
            }
 
            // Add these neighbors to the cloned graph node
            m[u].neighbors.Add(m[neighbor]);
        }
    }
 
    // Return the address of cloned src Node
    return m[src];
}
 
// Build the desired graph
static GraphNode BuildGraph()
{
    /*
    Given Graph:
    1--2
    | |
    4--3
    */
    GraphNode node1 = new GraphNode(1);
    GraphNode node2 = new GraphNode(2);
    GraphNode node3 = new GraphNode(3);
    GraphNode node4 = new GraphNode(4);
    node1.neighbors = new List<GraphNode> { node2, node4 };
    node2.neighbors = new List<GraphNode> { node1, node3 };
    node3.neighbors = new List<GraphNode> { node2, node4 };
    node4.neighbors = new List<GraphNode> { node3, node1 };
    return node1;
}
 
// A simple bfs traversal of a graph to
// check for proper cloning of the graph
static void Bfs(GraphNode src)
{
    Dictionary<GraphNode, bool> visit = new Dictionary<GraphNode, bool>();
    Queue<GraphNode> q = new Queue<GraphNode>();
    q.Enqueue(src);
    visit[src] = true;
    while (q.Count > 0)
    {
        GraphNode u = q.Dequeue();
Console.WriteLine("Value: " + u.val);
List<GraphNode> v = u.neighbors;
foreach (GraphNode neighbor in v)
{
if (!visit.ContainsKey(neighbor))
{
visit[neighbor] = true;
q.Enqueue(neighbor);
}
}
}
}
 
static void Main(string[] args)
{
GraphNode src = BuildGraph();
GraphNode clone = CloneGraph(src);
Console.WriteLine("Original Graph: ");
Bfs(src);
Console.WriteLine("Cloned Graph: ");
Bfs(clone);
}
}
 
 
//This code is contributed by shivamsharma215

Output

BFS Traversal before cloning
Value of Node 1
Address of Node 0x1b6ce70
Value of Node 2
Address of Node 0x1b6cea0
Value of Node 4
Address of Node 0x1b6cf00
Value of Node 3
Address of Node 0x1b6ced0

BFS Traversal after cloning
Value of Node 1
Address of Node 0x1b6e5a0
Value of Node 2
Address of Node 0x1b6e5d0
Value of Node 4
Address of Node 0x1b6e620
Value of Node 3
Address of Node 0x1b6e670

Time Complexity: O(V+E) where V is the number of vertices and E is the number of edges in the graph.
Auxiliary Space: O(V), since a map is used to store the graph nodes which can grow upto V.

Clone an undirected graph with multiple connected components

C

Chirag Agarwal

Improve

Previous Article

A Peterson Graph Problem

Introduction to Graph Coloring

Similar Reads

What is Undirected Graph? | Undirected Graph meaning

An undirected graph is a type of graph where the edges have no specified direction assigned to the them. Characteristics of an Undirected Graph:Edges in an undirected graph are bidirectional in nature.In an undirected graph, there is no concept of a "parent" or "child" vertex as there is no direction to the edges.An undirected graph may contain loo

Clone an undirected graph with multiple connected components

Given an undirected graph with multiple connected components, the task is to clone the graph. Cloning a graph with a single connected component can be seen here. Examples: An example of an undirected graph with 3 connected components: Approach: The idea is to follow the same approach posted for cloning connected graph, but with every node so that w

Convert the undirected graph into directed graph such that there is no path of length greater than 1

Given an undirected graph with N vertices and M edges and no self loops or multiple edges. The task is to convert the given undirected graph into a directed graph such that there is no path of length greater than 1. If it is possible to make such a graph then print two space-separated integers u and v in M lines where u, v denotes source and destin

Convert undirected connected graph to strongly connected directed graph

Given an undirected graph of N vertices and M edges, the task is to assign directions to the given M Edges such that the graph becomes Strongly Connected Components. If a graph cannot be converted into Strongly Connected Components then print "-1". Examples: Input: N = 5, Edges[][] = { { 0, 1 }, { 0, 2 }, { 1, 2 }, { 1, 4 }, { 2, 3 }, { 3, 4 } } Ou

Clone a Directed Acyclic Graph

A directed acyclic graph (DAG) is a graph which doesn't contain a cycle and has directed edges. We are given a DAG, we need to clone it, i.e., create another graph that has copy of its vertices and edges connecting them. Examples: Input : 0 - - - > 1 - - - -> 4 | / \ ^ | / \ | | / \ | | / \ | | / \ | | / \ | v v v | 2 - - - - - - - - -> 3

Maximum cost path in an Undirected Graph such that no edge is visited twice in a row

Given an undirected graph having N vertices and M edges and each vertex is associated with a cost and a source vertex S is given. The task is to find the maximum cost path from source vertex S such that no edge is visited consecutively 2 or more times. Examples: Input: N = 5, M = 5, source = 1, cost[] = {2, 2, 8, 6, 9}, Below is the given graph: Ou

Print all the cycles in an undirected graph

Given an undirected graph, print all the vertices that form cycles in it. Pre-requisite: Detect Cycle in a directed graph using colors In the above diagram, the cycles have been marked with dark green color. The output for the above will be 1st cycle: 3 5 4 6 2nd cycle: 5 6 10 93rd cycle: 11 12 13 Approach: Using the graph coloring method, mark all

Product of lengths of all cycles in an undirected graph

Given an undirected and unweighted graph. The task is to find the product of the lengths of all cycles formed in it.Example 1: The above graph has two cycles of length 4 and 3, the product of cycle lengths is 12. Example 2: The above graph has two cycles of length 4 and 3, the product of cycle lengths is 12. Approach: Using the graph coloring metho

Program to find Circuit Rank of an Undirected Graph

Given the number of Vertices and the number of Edges of an Undirected Graph. The task is to determine the Circuit rank. Circuit Rank: The Circuit rank of an undirected graph is defined as the minimum number of edges that must be removed from the graph to break all of its cycles, converting it into a tree or forest. Examples: Input :Edges = 7 , Vert

Find if an undirected graph contains an independent set of a given size

Given an undirected graph, check if it contains an independent set of size k. Print 'Yes' if there exists an independent set of size k. Print 'No' otherwise. Independent Set: An independent set in a graph is a set of vertices that are not directly connected to each other. Example 1: Input : K = 4, graph = [[1, 1, 0, 0, 0], [1, 1, 1, 1, 1], [0, 1, 1

Article Tags :

Practice Tags :