Clone an Undirected Graph- DSA Solution

/ DSA / By
Spread the love
Skylinewebz

It has previously been detailed how to clone a Binary Tree and LinkedList using random pointers. The concept of graph copying is essentially the same.

The goal is to perform a BFS traversal of the graph and create a clone node—a replica of the original node—while visiting a node. A clone node is already present if a node that has already been visited is encountered.

How can I monitor the nodes that have been visited or cloned? Maintaining all of the previously generated nodes requires a hash map or map. Important stores: The original node’s address or reference Value shops: Address/Reference of the Cloned Node A duplicate of every node in the graph has been created.

How are clone nodes connected? Visit all of the neighboring nodes for u, find the corresponding clone node for each neighbor (or create one if none exists), and then push into the neighboring vector of the cloneNodeU node. This process is done while visiting the neighboring vertices of a node u to obtain the corresponding cloned node for u, which we’ll call cloneNodeU.

How can I tell whether the cloned graph is accurate? Before and after the graph is cloned, perform a BFS traversal. In BFS traversal, show a node’s value in addition to its address or reference. Examine the node order; if the values are the same but the address or reference varies between the two traversals, the cloned graph is accurate.

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.

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