Clone Graph I

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

A graph is defined below:
struct Node {
vector<Node *> neighbors;
}

Idea: Bread First Search.

Difficulties: How to identify visited nodes. Otherwise, cycles will lead to a infinite loop!

Solution: Use map <Node *, Node *> to record the visited nodes. Key is the pointer in original graph and value is the pointer in the copied graph.

C++:
01 #include <map>
02 #include <iostream>
03 #include <queue>
04 #include <vector>
05 using namespace std;
06 
07 struct Node{
08     vector <Node *> neighbors;
09 };
10 typedef map<Node*, Node*> Map;
11 
12 Node * copy(Node * graph)
13 {
14     if(!graph)
15         return NULL;
16     Map map;
17     queue <Node *> q;
18     Node *graphCopy=new Node();
19     map[graph]=graphCopy;
20     q.push(graph);
21     while(!q.empty()){
22         Node *node=q.front();
23         q.pop();
24         int n=node->neighbors.size();
25         for(int i=0;i<n;i++){
26             Node *neighbor=node->neighbors[i];
27             if(map.find(neighbor)==map.end()){
28                 Node *p=new Node();
29                 map[node]->neighbors.push_back(p);
30                 map[neighbor]=p;
31                 q.push(neighbor);
32             }
33             else{
34                 map[node]->neighbors.push_back(map[neighbor]);
35             }
36         }
37     }
38     return graphCopy;
39 }
Advertisements
This entry was posted in Graph, Hashtable and Map. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s