首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。