clone graph with dfs & bfs

Posted on |

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.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
 struct UndirectedGraphNode {
  int label ;
  vector<UndirectedGraphNode *> neighbors ;
  UndirectedGraphNode(int x) : label(x) {};
};
//graph traversing by bfs
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]; 
 }