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; } |

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

+1Thanks. I would try my best to add it.

+4@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.

+3@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…

0In 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.

0As none of nodes’ neighbor is D,can D push into the queue?And can D be copied? Sorry,My English is so bad.Do you understand what is say?

0I just think Breadth-first can only be used in Connected Graph.if the Graph is not a Connected Graph,Then the solution is wrong.

0I think you are correct. If the graph is disconnected, the above code won’t be able to clone the graph as you will never be able to discover any components that are not reachable from the given node.

If you want to copy a disconnected graph you will need to have access to each and every disconnected component – via a node.

0Oh, 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?

0Guess 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…

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

+5The root is A, so the graph is A->B in this case

0To embed your code, please use

.

0thank u this is what i am loking for

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

0I’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!

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

0Believe 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 : )

0You are using BFS.

Actually I was interviewed with this question yesterday.

And I used DFS. The following are my codes:

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

0Thanks for your code.

0I 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)

0Sorry, my mistake. It works. Awesome

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

+2sorry,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?

+1IMHO, 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. : )

+2@1337c0d3r

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

plz clarify soon

0By 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.

0In 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;

}

0typedef 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]);

}

}

}

0IMHO, 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.

+7how di you post the type of codes ? “with color”

0IMHO, 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.

0using 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;

}

0seems 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];

}

0// 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;

}

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

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

0we 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

000why i can not use OJ ?

0god! , why the disscuss need another count

0Neat, 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.

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

0This two lines makes it returns the original graph.

0I 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.

0where is part II ??

+1thanks

0Does 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?

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

+2Java Version

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

-10Breath first and Depth first Java code

+3Node node = queue.poll();

I am new to Java. I got “Type mismatch: cannot convert from Object to CloneGraph.Node CloneGraph.java” for the above line. How to implicitly cast the object type?

Thanks,

April

0unordered_map, queue. You used too many helpers.

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

0without using a hashmap

000can not tolerant with the post system

0Pingback: LeetCode | techinterviewsolutions

Pingback: LeetCode | Technical interview solutions

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

More interview questions here

0Maybe I did not understand this question correctly. But as far as I know, there are usually 3 ways of representing graph which are as follows.

* Adjacency list

* Adjacency matrix

* Incidence matrix

Cloning either of them require iterating the graph. A deep copying of the data structure that representing the graph is good enough.

So I think this question has nothing to do with breadth first search or depth first search. If a string is used to represent the graph, then a copy of the string should be good enough.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

#include

std::string CloneGraph(const std::string &g)

{

return g;

}

00All the above solutions will only work, if all nodes are reachable from the initial node. Or am i incorrect in this assumption

0using namespace std;

struct Node{

int data;

vector neighbors;

};

typedef std::map HASH;

static HASH hash_table;

static void cloneDFS(Node* graph, Node* graphcopy);

static void cloneDFS(Node* graph, Node* graphcopy)

{

int i;

if (!graph) return ;

if (hash_table.find(graph) == hash_table.end()) {

hash_table[graph] = graphcopy;

graphcopy->data = graph->data;

}

for (i=0; ineighbors.size(); i++) {

if (hash_table.find(graph->neighbors[i]) == hash_table.end()) {

Node* neighbor = new Node();

graphcopy->neighbors.push_back(neighbor);

cloneDFS(graph->neighbors[i], neighbor);

}else{

graphcopy->neighbors.push_back(hash_table[graph->neighbors[i]]);

}

}

}

void test_cgp1()

{

Node* n1 = new Node(); n1->data = 1;

Node* n2 = new Node(); n2->data = 2;

Node* n3 = new Node(); n3->data = 3;

Node* n4 = new Node();

n1->neighbors.push_back(n2);

n2->neighbors.push_back(n1);

n2->neighbors.push_back(n3);

n3->neighbors.push_back(n2);

cloneDFS(n1, n4);

printf(“clone graph partI over!\n”);

}

0Great! Thanks

0Pingback: Clone Graph | moonstonelin