[数据结构与算法]2021-10-10 leetcode 数据结构 133.克隆图 DFS 深浅拷贝解释以及区别 C++

题目

解释

核心：深拷贝（本篇blog最后有解释）
建立新的内存，将该图复制到新的内存中

思路

DFS&map
DFS：利用DFS遍历，并复制到新的结构体中

AC代码

/*
// Definition for a 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;
    }
};
*/

class Solution {
private:
    map<Node*, Node*>visited;//<原图中的结点，深拷贝图中的结点>
public:
    Node* cloneGraph(Node* node) {
        if(!node) 
            return NULL;
        if(visited.count(node))//若map中包含该结点,则直接返回该结点，避免绕圈
            return visited[node];//最后返回到neighbors中的都是visited[node],即深拷贝的结点
        else{
            Node *cloneNode =new Node(node->val);//创建一个新结点，让cloneNode->val = node->val
            visited[node] = cloneNode;
            for(Node* n : node->neighbors)//遍历node的相邻结点
                cloneNode->neighbors.push_back(cloneGraph(n));//dfs,不断访问相邻结点
            return cloneNode;
        }
    }
};

关于深拷贝和浅拷贝

浅拷贝（shallowCopy）只是增加了一个指针指向已存在的内存地址
深拷贝（deepCopy）是增加了一个指针并且申请了一个新的内存，使这个增加的指针指向这个新的内存。

深拷贝和浅拷贝最根本的区别在于是否真正获取一个对象的复制实体，而不是引用。

eg：对于A，B对A进行浅拷贝，C对A进行深拷贝
现释放A的内存：
B由于指向A的地址，受A影响，随A的释放而释放。
C不受影响。