clone graph with dfs & bfs

leetcode 133, the solution is traversing the graph, so either bfs or dfs should work.

dfs works like a stack, take an example when processA is running, inside processB is invoked, then processA hang, and go into processB; as processB is running, inside processC is invoked, then processB hanged, and go into processC. e.t.c. so the finished order is from innerest to outest. dfs will always traverse all possibilities, then return to the outest layer.

in clone graph, e.g.

#0, 1,  2
#1, 2
#2, 2

dfs process as:

first deal with first line, element 0, which trick element 1, so process goes to second line, and trick element 2, so go to third line(done), then return to second line(done), then return to first line, trick second neighbor 2 go on…

bfs works different, during processA running, processB is invoked, will still run processA to done, but also push processB to job queue, which will run next time. so using bfs, usually has a queue variable to mark unfinished jobs.

 
 struct  {
  int label ;
  vector<UndirectedGraphNode *> neighbors ;
  UndirectedGraphNode(int x) : label(x) {};
};
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){
      if(!node) return nullptr ;
      UndirectedGraphNode *c_node = new UndirectedGraphNode(node->label);
      queue<UndirectionGraphNode*> qlist ;
      unorder_map<int, UndirectionGraphNode*> map;
      map[c_node->label] = c_node ;
      qlist.push(c_node);
      UndirectedGraphNode cur, neighbor = nullptr;
      
      while(!qlist.empty()){
        cur = qlist.front(); qlist.pop();
        for(int i=0; i<cur->neighbors.size(); i++){
         neighbor =  cur->neighbors[i];
         if(map.find(neighbor->label))
         {
           c_node->neighbors.push_back(neighbor);
         }else{
           UndirectedGraphNode *tmp = new UndirectedGraphNode(neighbor->label);
           c_node->neighbors.push_back(tmp); 
           map[tmp->label] = tmp ;
           qlist.push(tmp);  //bfs idea: find new node, push it to queue and deal
           // with it in next while loop
         }
      }
    }
      return map[c_node->label];
  }
 //dfs
 void dfs(UndirectedGraphNode* node, unorder_map<int, UndirectionGraphNode*>& map)
 {
    UndirectedGraphNode * c_node = nullptr;
    if(!map.find(node->label)){
      c_node = new UndirectedGraphNode(node->label);
      map[c_node->label] = c_node;
    }else{
      c_node = map.find(node->label);
    }
    UndirectedGraphNode* nei;
    for(int i=0; i<node->neighbors.size(); i++){
        nei = node->neighbors[i];
        if(map.find(nei->label)){
          c_node->neighbors.push_back(nei);
        }else{
          dfs(nei, map);
        }
      }
  }
 UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node){
   unorder_map<int, UndirectionGraphNode*> map;
   dfs(node, map);
   return map[node->label]; 
 }

clone graph with dfs & bfs

近期文章

近期评论

标签

热门

文章归档

分类目录

功能