题目：
给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node {
public:int val;vector<Node*> neighbors;Node() {val = 0;neighbors = vector<Node*>();}Node(int _val) {val = _val;neighbors = vector<Node*>();}Node(int _val, vector<Node*> _neighbors) {val = _val;neighbors = _neighbors;}
};
思路
首先我们了解下浅拷贝，如果在类中没有显式地声明一个拷贝构造函数，编译器将会自动生成一个默认的拷贝构造函数，该构造函数完成对象之间的浅拷贝。这会带来数据安全方面的隐患，如含有指针的类进行拷贝，对象和他的拷贝将共用同一指针为避免出现此类问题，在进行赋值之前，为指针类型的数据成员另辟了一个独立的内存空间，实现深拷贝。深拷贝后对象和他的拷贝完全无关联但数值、结构完全相等。
对于本题而言，我们需构建一张与原图完全无关联但数值、结构完全相等的拷贝图。因此，我们需要遍历整张图，并在遍历的过程中建立拷贝图，首先想到常见图算法BFS和DFS。为了保证图的每个节点只访问一次避免死循环，我们使用禁忌表（vector、unordered_map）来存储已访问过的点。
注意vector在类中初始化时会出现的问题，错误方法在编译过程中会被误认为函数原型。
vector<Node*> visited = vector<Node*>(101, nullptr); //true
vector<Node*> visited (101, nullptr); //false
方法一：DFS（使用vector作为visited）
class Solution {
private:vector<Node*> visited = vector<Node*>(101, nullptr);
public:Node* cloneGraph(Node* node) {if(node == nullptr) return node;if(visited[node->val] != nullptr) return visited[node->val];Node* cloneNode = new Node(node->val);visited[node->val] = cloneNode;for(auto neighbor : node->neighbors) {cloneNode->neighbors.emplace_back(cloneGraph(neighbor));}return cloneNode;}
};
复杂度分析
- 时间复杂度：，其中 表示节点数量。深度优先搜索遍历图的过程中每个节点只会被访问一次。
- 空间复杂度：。禁忌表需要的空间，递归调用栈需要的空间，其中是图的深度，经过放缩可以得到 ，因此总体空间复杂度为 。
方法二：BFS（使用unordered_map作为visited）
class Solution {
public:Node* cloneGraph(Node* node) {if (node == nullptr) return node;unordered_map<Node*, Node*> visited;queue<Node*> Q;Q.push(node);visited[node] = new Node(node->val);while(!Q.empty()) {auto nowNode = Q.front();Q.pop();for(auto neighbor : nowNode->neighbors) {if (visited.find(neighbor) == visited.end()) {visited[neighbor] = new Node(neighbor->val);Q.push(neighbor);}visited[nowNode]->neighbors.emplace_back(visited[neighbor]);}}return visited[node];}
};
复杂度分析
- 时间复杂度：，其中表示节点数量。广度优先搜索遍历图的过程中每个节点只会被访问一次。
- 空间复杂度：。禁忌表使用 的空间。广度优先搜索中的队列在最坏情况下会达到 的空间复杂度，因此总体空间复杂度为 。
相似题目：
LeetCode 138 复制带随机指针的链表