clone graph(c++ code)

LeetCode clone graph

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

 思路1：BFS，注意这种方法需要graph是connected的。

Node *clonegraph(Node *graph){
  if(graph == NULL) return NULL;
  map<Node *, Node *> visited;
  queue<Node *> q;
  q.push(graph);
  Node *clonegraph = new Node();
  visited[graph] = clonegraph;
  while(!q.empty()){
    Node *cur = q.front();
    vector<Node *> curadj = cur->neighbors;
    q.pop();
    for(int i = 0; i < curadj.size(); i++){
        if(visited.find(curadj[i]) == visited.end()){
            Node *adj = new Node();
           q.push(curadj[i]);
            visited[cur]->neighbors.push_back(adj);
            visited[curadj[i]] = adj;            
        }
       else visited[cur]->neighbors.push_back(visited[curadj[i]]);
    }

 }
  return clonegraph;
}

思路2： DFS，同上，需要所有nodes reachable from given node.
Node *dfs(Node *graph, map<Node *, Node *>  &visited){
  if(visited.find(graph) != visited.end()) return visited[graph];
  Node *clonegraph = new Node();
  visited[graph] = clonegraph;
  for(int i = 0; i < graph->neighbors.size(); i++){
    Node *neighbor = graph->neighbors[i];
    clonegraph->neighbors.push_back(dfs(neighbor, visited));
 }

 return clonegraph;
}

Node *clonegraph(Node *graph){
  if(!graph) return NULL;
  map<Node *,Node *>visited;
  return dfs(graph, visited);
}