"Clone Graph"

/*

*I used BFS to traverse the whole graph, a queue to store the neighbor, which will be accessed next loop

*mapGraph to store the created node. map <label, UndirectedGraphNode *>

*/

----------------------my code-----------------------------

```
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
queue<UndirectedGraphNode *> q;
UndirectedGraphNode *source = NULL; // viariable stores the given graph node
UndirectedGraphNode *root = NULL;
map<int, UndirectedGraphNode *>mapGraph;//store the cloned node <label, UndirectedGraphNode *>
vector<UndirectedGraphNode *> neighbors; //for convenience, stores the neighbors from source.
int is_first = 1, i, size;
if(node == NULL)
return root;
q.push(node);//store the first node;
while(!q.empty())
{
source = q.front();
UndirectedGraphNode *target = new UndirectedGraphNode(source -> label);
mapGraph[source -> label] = target;
if(is_first)// just store the root, which is returned value in future
{
root = target;
is_first = 0;
}
neighbors = source -> neighbors;//store the neighbor from source, just for convenient to use in the next
size = neighbors.size();
for(i = 0; i < size; i++)//traversing the neighbors
{
// weather the node is created already, here using the map to store the created node
// if the node is not in map, just create it and label it, add it in the map.
if(mapGraph.find(neighbors[i] -> label) == mapGraph.end())
{
UndirectedGraphNode *tmp = new UndirectedGraphNode(neighbors[i] -> label);
mapGraph[tmp -> label] = tmp;
(target -> neighbors).push_back(tmp);
}
else//
{
(target -> neighbors).push_back(mapGraph[neighbors[i] -> label]);
}
q.push(neighbors[i]);
}
q.pop();
}
return root;
}
```