Clone given Graph

Given a graph with an adjacency list, we aim to clone the complete graph with edges. Cloning does creates a new memory for similar data. Let us understand this with a three-node example graph.

We can solve this problem using either DFS or BFS. Let’s solve this problem using DFS. Our Graph object contains the below data.

1. GraphNode
   1. An Integer Data
   2. An Adjacency list (which contains edges).
2. A Map that keeps track of all visited nodes in the graph.

Let’s see the code for this algorithm using DFS.

GraphNode* cloneGraph(GraphNode *node, map<int, GraphNode*> &visit) {
	if (visit.find(node->val) != visit.end()) {
		return visit.at(node->val);
	}
        // Creates a new copy node of its original node.
	GraphNode *copy = new GraphNode(node->val);
	visit[node->val] = copy;
	list<GraphNode*>::iterator valItr; // = val->adjList.begin();
	for (valItr = node->adjList->begin(); valItr != node->adjList->end(); valItr++) {
		copy->adjList->push_back(cloneGraph(*valItr, visit));
	}
	return copy;
}

This algorithm runs with complexity O(V * E), with space O(V). Complete code for this algorithm is as follows.

// Complexity: O(V * E), Space: O(V).
// Output
Original Graph:
10-->20  30
20-->10  30
30-->10  20
Cloned Graph:
10-->20  30
20-->10  30
30-->10  20

It is all about cloning a graph with an adjacency list. I hope this helps you understand the algorithm. If you have any better solution to solve this problem, please let our readers know by commenting below. Happy Learning.