方法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 }
原文：http://www.cnblogs.com/boring09/p/4266525.html