图的复制（类似与复杂链表的复制）
clone-graph
http://www.nowcoder.com/questionTerminal/5ec76def9d7b420794091727a97f0dc6
分步进行
（1）首先通过DFS深度优先遍历，复制节点，使用一个map来保存原来节点A和复制节点A' 即map[A]=A'
（2）通过遍历map中的key值，找到原图中节点的所有邻居节点，将该邻居节点对应的复制节点添加到key值对应的复制节点的邻居节点即可
另外注意这个题很好通过，因为这个题似乎只有一个很简单的测试用例，我看到有些人的写法是错误的这题也通过了，而且直接还回node节点居然也可以过，所以想练手的同学们可以做leetcode上的原题：leetcode133 Clone Graph 链接：https://leetcode-cn.com/problems/clone-graph/
unordered_map<UndirectedGraphNode*, UndirectedGraphNode*> mp;
void dfs(UndirectedGraphNode* node) {
if (node == nullptr) { return; }
if (mp.count(node)) { return; }
UndirectedGraphNode *copyNode = new UndirectedGraphNode(node->label);
mp[node] = copyNode;
for (auto n : node->neighbors) {
dfs(n);
}
}
UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
UndirectedGraphNode* oldNode = node;
dfs(node);
for (auto n : mp) {
UndirectedGraphNode *first = n.first;
for (int i = 0; i < first->neighbors.size(); i++) {
n.second->neighbors.push_back(mp[first->neighbors[i]]);
}
}
return mp[oldNode];
} 
投递快手等公司10个岗位 >
