首页 > 代码库 > Leetcode#133 Clone Graph

Leetcode#133 Clone Graph

原题地址

 

方法I,DFS

一边遍历一边复制

借助辅助map保存已经复制好了的节点

对于原图中每个节点,如果已经复制过了,直接返回新节点的地址,如果没复制过,则复制并加入map中,接着依次递归复制其兄弟。

代码:

 1 map<UndirectedGraphNode *, UndirectedGraphNode *> old2new; 2  3 UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { 4         if (!node) 5             return NULL; 6         if (old2new.find(node) != old2new.end()) 7             return old2new[node]; 8          9         UndirectedGraphNode *newNode = new UndirectedGraphNode(node->label);10         old2new.insert(pair<UndirectedGraphNode *, UndirectedGraphNode *>(node, newNode));11         for (auto n : node->neighbors)12             newNode->neighbors.push_back(cloneGraph(n));13         return newNode;14 }

 

方法II,BFS

一边遍历一边复制

同样借助一个辅助map保存复制过的节点,还需要一个set保存已经遍历过的节点

代码:

 1 UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) { 2          if (!node) 3             return NULL; 4              5          map<UndirectedGraphNode *, UndirectedGraphNode *> old2new; 6          unordered_set<UndirectedGraphNode *> copied; 7          queue<UndirectedGraphNode *> que; 8           9          old2new.insert(pair<UndirectedGraphNode *, UndirectedGraphNode *>(node, new UndirectedGraphNode(node->label)));10          que.push(node);11          while (!que.empty()) {12              UndirectedGraphNode *front = que.front();13              que.pop();14              if (copied.find(front) != copied.end())15                 continue;16              for (auto n : front->neighbors) {17                  if (old2new.find(n) == old2new.end()) {18                      UndirectedGraphNode *newNode = new UndirectedGraphNode(n->label);19                      old2new.insert(pair<UndirectedGraphNode *, UndirectedGraphNode *>(n, newNode));20                      que.push(n);21                  }22                  old2new[front]->neighbors.push_back(old2new[n]);23              }24              copied.insert(front);25          }26          27          return old2new[node];28  }

 

Leetcode#133 Clone Graph