解题思路:
本质是遍历图的所有顶点,然后将每个节点深拷贝到新的顶点,图的遍历自然想到DFS和BFS两种方法
问题的关键在于如何深拷贝每个顶点:
- 首先,用一个哈希表存放旧顶点和新顶点,这样在访问旧顶点的时候,可以快速定位新的顶点
- 其次,遍历过程中,不能用构造函数直接拷贝每个顶点的邻居,需要单独拷贝
代码
方法一:DFS
class Solution {
public:
unordered_map<Node*, Node*> vis; //标记旧顶点到新顶点的映射
Node* cloneGraph(Node* node) {
if (node == nullptr) return nullptr;//顶点为空的情况
if (vis.find(node) != vis.end()) { //如果发现vis中已经访问过旧顶点,直接返回对应的新顶点
return vis[node];
}
Node *clone = new Node(node->val); //构造一个克隆的新顶点,主要不能直接调用构造函数拷贝邻居
vis[node] = clone; //标记已经访问过当前顶点node,并对应相应的克隆顶点
for (auto &nb : node->neighbors) { //对每个邻居加入到新的顶点中,进一步调用cloneGraph
clone->neighbors.emplace_back(cloneGraph(nb));
}
return clone; //返回克隆的新顶点
}
};方法二:BFS
class Solution {
public:
Node* cloneGraph(Node* node) {
if (node == nullptr) return nullptr;
queue<Node*> que; // 用来BFS遍历时,存放顶点
unordered_map<Node*, Node*> vis; // 标记已经访问过的顶点,并映射到克隆的顶点上
Node *clone = new Node(node->val); // 创建当前顶点的克隆顶点
que.emplace(node);
vis[node] = clone; // 标记当前顶点node已经访问过
while (!que.empty()) {
Node* p = que.front(); que.pop(); // 取出队首的顶点
for (auto & nb : p->neighbors) {
if (vis.find(nb) == mp.end()) { //如果邻居没有访问过,加入到队列中,并且存放到哈希表中
vis[nb] = new Node(nb->val);
que.emplace(nb);
}
mp[p]->neighbors.emplace_back(vis[nb]);//依次将每个顶点加入到克隆顶点的邻居数组中
}
}
return mp[node]; // 返回node对应的克隆顶点,也j
}
};