## Clone Graph Part I

May 30, 2012 in Uncategorized

Clone a graph. Input is a Node pointer. Return the Node pointer of the cloned graph.

A graph is defined below:

struct Node {

vectorneighbors;

}

**Hint:**

There are two main ways to traverse a graph. Do you still remember them? Could you tell if the graph is directed or undirected?

**Solution:**

There are two main ways to traverse a graph: *Breadth-first* or *Depth-first*. Let’s try the Breadth-first approach first, which requires a queue. For the Depth-first approach, please see Clone Graph Part II.

How does the breadth-first traversal works? Easy, as we pop a node off the queue, we copy each of its neighbors, and push them to the queue.

A straight forward breadth-first traversal seemed to work. But some details are still missing. For example, how do we connect the nodes of the cloned graph?

Before we continue, we first need to make sure if the graph is directed or not. If you notice how Node is defined above, it is quite obvious that the graph is a directed graph. Why?

For example, A can have a neighbor called B. Therefore, we may traverse from A to B. An undirected graph implies that B can always traverse back to A. Is it true here? No, because whether B could traverse back to A depends if one of B’s neighbor is A.

The fact that B can traverse back to A implies that the graph may contain a cycle. You must take extra care to handle this case. Imagine that you finished implementing without considering this case, and later being pointed out by your interviewer that your code has an infinite loop, yuck!

Let’s analyze this further by using the below example:

Assume that the starting point of the graph is A. First, you make a copy of node A (A2), and found that A has only one neighbor B. You make a copy of B (B2) and connects A2->B2 by pushing B2 as A2′s neighbor. Next, you find that B has A as neighbor, which you have already made a copy of. Here, we have to be careful not to make a copy of A again, but to connect B2->A2 by pushing A2 as B2′s neighbor. But, how do we know if a node has already been copied?

Easy, we could use a hash table! As we copy a node, we insert it into the table. If we later find that one of a node’s neighbor is already in the table, we do not make a copy of that neighbor, but to push its neighbor’s copy to its copy instead. Therefore, the hash table would need to store a mapping of key-value pairs, where the key is a node in the original graph and its value is the node’s copy.

Let’s implement the code!

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | typedef unordered_map<Node *, Node *> Map; Node *clone(Node *graph) { if (!graph) return NULL; Map map; queue<Node *> q; q.push(graph); Node *graphCopy = new Node(); map[graph] = graphCopy; while (!q.empty()) { Node *node = q.front(); q.pop(); int n = node->neighbors.size(); for (int i = 0; i < n; i++) { Node *neighbor = node->neighbors[i]; // no copy exists if (map.find(neighbor) == map.end()) { Node *p = new Node(); map[node]->neighbors.push_back(p); map[neighbor] = p; q.push(neighbor); } else { // a copy already exists map[node]->neighbors.push_back(map[neighbor]); } } } return graphCopy; } |

Chaos said on May 30, 2012

nice job:) and adding this problem to OJ list would be preferable

+21337c0d3r said on May 31, 2012

Thanks. I would try my best to add it.

+5andydale said on April 4, 2014

@1 337c0d3r,

Hi,

Please let me know what do you think about following approach,

Instead of using hash table to store the prevoiusly cloned nodes / visited nodes. We can keep a pointer in original graph ( cloned_node ), and set it at time of clone node creation and use it at time of visiting it as a visited neighbour of a new node.

I know it leads to O(V) space overhead in original graph, but it provides actual O(1) access time and avoid requirements to have a lable in nodes.

+3Venki said on May 31, 2012

@1337c0d3r,

I am not clear about graph representation. If the graph is having more than one SCC, how can it be represented using Node structure? For example, a directed graph with four nodes, A, B, C and D. Assume we have the directed edges, (A, B), (B, A), (D, C), (B, C) and (A, C) where pair (X, Y) represents directed edge from X to Y.

I was unable to construct graph for the above input. Am I missing anything? Please correct me…

01337c0d3r said on May 31, 2012

In your above example,

Node A would have neighbors B, C.

Node B would have neighbors A, C.

Node C would have 0 neighbor.

Node D would have neighbor C.

Your job is to clone the above graph, and return a copy of its graph.

0Venki said on May 31, 2012

Oh, okay. I got it. Thanks. I face the above problem when I tried to create few test cases. But it worked fine for the partial graph. To add further, we can extend the Node structure with second level pointer that will point next component of the graph.

Any inputs?

0Hector said on June 12, 2012

Guess the problem was to clone a “Connected” graph. Consider graph:

A->B<-C

Code above start from A will stop at node B. Node C will be ignored…

+2ZhigangZhao said on July 23, 2013

this graph can not be represented using only a node pointer. and it is not the case here.

+4Sanjay Pandey said on June 20, 2012

To embed your code, please use

.

0عرب برامج said on July 12, 2012

thank u this is what i am loking for

0Jinhui said on July 16, 2012

I cannot help saying this is really a nice work with clear explanation. Thanks

0temp123 said on August 8, 2012

I’m not sure if I got the problem right.

I don’t why you can represent a graph as a node.

A graph is defined below:

struct Node {

vector neighbors;

}

What if the graph is not connected?

I also don’t know why this is difficult — graph is always represented by data structures. Can we just copy the data representation? Do we have to traverse the graph?

Thanks!

+2moussa said on January 30, 2013

I think you are right. The code will work for spanning tree but Forest which consists of multiple disconnected trees.

0Nison said on May 10, 2013

Believe the question is not clear by its definition. Intuitively, as the Graph is defined by Node, it is supposed to be connected.

And by further reflection, a graph is usually defined as array of pointer of linked list, if clone a graph, the possible solution is simply combination of the individual graph clone, together with the final combination of the individual graphs into the whole graph.

But in latter case, the graph is not given by a node, rather, it should be given as a pointer of array of pointer of linked list. In cases when graph is represented in other form, the solution is similar.

So up to now, the solution of the creator of this topic and other great guys are focusing on the individual graph clone — the core of the whole graph clone. You are all great guys and I have benefit a lot : )

0Chao Chen said on August 10, 2012

You are using BFS.

Actually I was interviewed with this question yesterday.

And I used DFS. The following are my codes:

Node* DFS(Node *Input, hash_map &hm){

if(hm.find(Input) != hm.end()){

return hm[Input];

}

Node *output = new Node();

hm[Input] = output;

for(int i = 0; i next.size();i++){

output->next.push_back(DFS(Input->next[i],hm));

}

return output;

}

+61337c0d3r said on August 11, 2012

Yup, DFS is another solution, which is actually considerably easier than the BFS solution.

0Eason said on October 9, 2013

Thanks for your code.

0Ethan said on March 7, 2014

I am not quite sure. But there seems a bug in the code.

The function return the cloned node. However, it accepts the original node and it is in recursive manner.

So the second visit on the recursive function will provide the wrong parameter (cloned node rather than original node)

0Ethan said on March 7, 2014

Sorry, my mistake. It works. Awesome

0Chao Chen said on August 10, 2012

And I guess that you can use my codes in your second part(I didn’t find part II).

+2jack said on August 13, 2012

sorry,I don’t understand this “if” part:

if (map.find(neighbor) == map.end()) {

Node *p = new Node();

map[node]->neighbors.push_back(p);

map[neighbor] = p;

q.push(neighbor);

}

if a copy doesn’t exist, an empty new node p was pushed to the end of one of graphCopy’s node’s neighbors vector table. Why push_back an empty new node, not a node from original graph node?

+1Nison said on May 10, 2013

IMHO, an empty new node was pushed…. the point is that, it is not only pushed into the vector, but also be added into the map, so the node in original graph and the node in new graph is “related to each other” by the bridge of map.

In first glance, it will only be put into the vector. But after thinking twice, we can notice that the neighbor will be put into the queue. And at the time the neighbor is pop out, we will traverse its neighbor — that’s the time we will edit “empty node ” p — node p now shows as “node”. By modification of node map[node], we actually modify node p.

So the connection is built through map, and the queue will serve as an coordinator to help decide who will be traversed first and who later.

Focus on the map and queue. They are the heart of the algorithm provided by this topic’s creator, if my guess is not wrong. : )

+2codez said on August 15, 2012

@1337c0d3r

i have the same doubt as Jack. y r we pushing an empty node?

plz clarify soon

01337c0d3r said on August 15, 2012

By pushing an empty node you are essentially making a copy of the node. You are to clone a graph, so essentially make a copy of each node and linking all of them together.

0jack said on August 16, 2012

In a graph, each node should have some data fields, such as “int data”.

Each node should have 2 parts:

struct Node {

int data;

vector neighbors;

}

+1nehaheights said on August 17, 2012

typedef unordered_map Map;

Map map;

void cloneDFS (Node *graph, Node *&graphCopy) {

if (!graph) return;

if(map.find(graph) == map.end())

{

graphCopy = new Node();

map[graph] = graphCopy;

map[graph]->data = graph->data;

}

int n = graph->neighbors.size();

for (int i = 0; i neighbors[i];

// no copy exists

if (map.find(neighbor) == map.end()) {

Node *p = new Node();

map[graph]->neighbors.push_back(p);

map[neighbor] = p;

map[neighbor]->data = neighbor->data;

cloneDFS(neighbor, p);

} else { // a copy already exists

map[graph]->neighbors.push_back(map[neighbor]);

}

}

}

0Nison said on May 10, 2013

IMHO, there are 3 aspects that you can improve your code.

1). The clone of parent node and clone of child node have some identical part. Those part could be simplified by recursive call. Yes, you did, but why clone neighbor twice, in the if statement under the true field?

2). Because of the void return type, you cannot benefit for its return information. So you made your choice to create the node before clone it, and then call recursive. But when calling recursively, you create another node using “new”, again. The will destroy the graph structure. Also, this will consume resources.

3). Another point is that because you select the cloned graph as an parameter, you have to declare it before the clone call. To avoid warning of uninitialized variable, you maybe choose to initialize it by new. This is not a fairly good choice IMO.

So, you refer to Chao Chen’s code. Why is his code so simple? Because

1) he use return type smartly, so as to avoid duplicate information

2) he separate steps clearly, no overlapping function

Let’s come back to your code, and I modify it according to your idea, as below. And you will see that it doesn’t work.

+7Nison said on May 10, 2013

IMHO, there are 3 aspects that you can improve your code.

1). The clone of parent node and clone of child node have some identical part. Those part could be simplified by recursive call. Yes, you did, but why clone neighbor twice, in the if statement under the true field?

2). Because of the void return type, you cannot benefit for its return information. So you made your choice to create the node before clone it, and then call recursive. But when calling recursively, you create another node using “new”, again. The will destroy the graph structure. Also, this will consume resources.

3). Another point is that because you select the cloned graph as an parameter, you have to declare it before the clone call. To avoid warning of uninitialized variable, you maybe choose to initialize it by new. This is not a fairly good choice IMO.

So, you refer to Chao Chen’s code. Why is his code so simple? Because

1) he use return type smartly, so as to avoid duplicate information

2) he separate steps clearly, no overlapping function

Let’s come back to your code, and I modify it according to your idea, as below. And you will see that it doesn’t work.

0renguo said on June 3, 2013

using namespace std;

struct node{

int data;

vector neighbors;

};

unordered_map m;

void cloneNeighbors(node*, node*);

node* cloneGraphDFS(node* graph){

if(!graph)

return NULL;

node* graphClone = new node;

graphClone->data = graph->data;

m[graph] = graphClone;

cloneNeighbors(graph, graphClone);

return graphClone;

}

void cloneNeighbors(node* origin, node* clone){

int n = origin->neighbors.size();

for(int i=0; ineighbors[i];

if(m.find(pNeighbor)== m.end()){

node* pNeighborClone = new node;

pNeighborClone->data = pNeighbor->data;

m[pNeighbor] = pNeighborClone;

m[origin]->neighbors.push_back(pNeighborClone);

cloneNeighbors(pNeighbor, pNeighborClone);

}

else{

m[origin]->neighbors.push_back(m[pNeighbor]);

}

}//for i

}

int main( )

{

node* root = new node;

root->data = 0;

node* node1 = new node;

node1->data = 1;

root->neighbors.push_back(node1);

node1->neighbors.push_back(root);

node * node2 = new node;

node2->data = 2;

node1->neighbors.push_back(node2);

node* graphClone = cloneGraphDFS(root);

return 0;

}

0Bin said on January 23, 2013

seems separate the node creating and relationship copying makes code more readable, this is my answer

class Node

{

public Node()

{

neighbors = new List();

}

public IList neighbors { get; private set; }

}

Node Copy(Node org)

{

if (null == org)

return null;

Queue wait = new Queue();

IDictionary map = new Dictionary();

wait.Enqueue(org);

while (wait.Count > 0)

{

var current = wait.Dequeue();

if (!map.ContainsKey(current))

{

Node copy = new Node();

map.Add(current, copy);

}

foreach (Node neighbor in current.neighbors)

{

if (!map.ContainsKey(neighbor))

{

wait.Enqueue(neighbor);

}

}

}

foreach (KeyValuePair pair in map)

{

foreach (Node neighbor in pair.Key.neighbors)

{

pair.Value.neighbors.Add(map[neighbor]);

}

}

return map[org];

}

0chen long said on March 11, 2013

// Type your C++ code and click the “Run Code” button!

// Your code output will be shown on the left.

// Click on the “Show input” button to enter input data to be read (from stdin).

#include

#include

#include

#include

#include

using namespace std;

struct Node {

Node(int value) : value(value) {}

Node(Node &rhs) {

if (&rhs == this) {return;}

this->value = rhs.value;

this->neighbors.resize(rhs.neighbors.size());

}

int value;

vector neighbors;

};

Node* clone(Node *node) {

if(node == 0) { return 0; }

map created;

queue to_expand;

int id = 0;

Node *copy = new Node(*node);

created[node] = copy;

to_expand.push(node);

while(!to_expand.empty()) {

// fetech the first node

Node *curr = to_expand.front();

to_expand.pop();

int n_size = curr->neighbors.size();

// copy the neighbors of curr_src into curr_dst.

for(int n_idx = 0; n_idx neighbors[n_idx];

// if we have created the copy, fill out the created one.

if(created.find(c) != created.end()) {

// cloned node alreayd exist.

created[curr]->neighbors[n_idx] = created[c][/c];

}else{

// no cloned node existed.

Node* n = new Node(*c);

// this is a new node, we need to fill out its neighbors as well.

// let’s register into the BFS queue for future explore.

created[curr]->neighbors[n_idx] = n;

created[c][/c] = n;

to_expand.push(c);

}

}

}

return copy;

}

int main() {

Node *src = new Node(100);

src->neighbors.push_back(new Node(101));

src->neighbors[0]->neighbors.push_back(src);

Node *dst = clone(src);

// cout <value << endl;

cout <value << endl;

cout <neighbors[0]->value << endl;

cout <neighbors[0]->neighbors[0]<< endl;

return 0;

}

0B l said on April 4, 2013

this code will run infinitely if the graph has a loop: A->B->C->A. is it right?

0overboming said on April 7, 2013

No, it’s breath first, A->C is already in the hashmap when C is on the top of the queue

0mars said on June 5, 2013

we are creating one copy and using pointers in the vector.. my concern is when we need to delete nodes the question comes who is responsible for free up memory and so need to be extra careful in deleting node..I would convert node* to some shared pointer so that ownership issues wil not arise

0Amax said on July 5, 2013

0answer said on July 5, 2013

0quleetcode said on August 9, 2013

why i can not use OJ ?

0wangjie said on October 14, 2013

god! , why the disscuss need another count

0Dev said on October 17, 2013

Neat, seems like a lot of different ways we can clone a graph. But which one is most efficient. and main question is do we really need to clone the whole graph. Good read, comments are even more interesting.

0Sagar said on November 10, 2013

Logic similar to what has been posted above, but used a queue…

0Ethan said on March 7, 2014

This two lines makes it returns the original graph.

0Sagar said on November 10, 2013

I have a question here.. Generally or rather mathematically, a graph is defined as a set of vertices and edges. Till now, whatever implementations I have made on graphs, I have made use of this property of graph and it actually helps in proper designing of the graph.

But, the definition given here contains just the neighbors of every Vertex. Now, this kinda scenario is good for this problem, but if say, we have to implement the Djikstra algo, then this may not be the best way of implementing a graph as we need to assign weights to the edges, which doesn’t quite seem possible here.

So, is it the case that we need to make new graph implementation per problem or would having an uber-graph with all properties be more helpful? I am also asking from the interviewing purposes. Is the structure always imposed upon us or we can make assumptions and go ahead?

Any suggestions would be highly appreciated.

0ldms020255 said on December 12, 2013

where is part II ??

+1biglong said on January 16, 2014

thanks

0Wei She said on February 8, 2014

Does this question have a flaw? Suppose we have a directed graph as follows:

A->B<-C

And, the input pointer points to B. How can I traverse this graph?

+2Ze Wang said on February 9, 2014

This is probably a matter of data structure, C is not accessible from A anyway.

+2Ethan said on March 7, 2014

Java Version

0Ethan said on March 7, 2014

There is a bug in the code. I should not have added clonedNeighbor into the queue. Here is the fixed code.

0Ethan said on March 7, 2014

0Ethan said on March 7, 2014

Breath first and Depth first Java code

+2Enihcam said on March 12, 2014

unordered_map, queue. You used too many helpers.

0Maduser Web said on July 3, 2014

Spent some time and found that using map is really a good idea.

0hgfeaon said on July 22, 2014

without using a hashmap

0hgfeaon said on July 22, 2014

0hgfeaon said on July 22, 2014

0hgfeaon said on July 22, 2014

can not tolerant with the post system

0Mission peace said on November 11, 2014

https://github.com/mission-peace/interview/wiki

More interview questions here

0