LeetCode克隆图BFS解法中mp[node]=first后为何仍能访问原节点邻接点

• 题目来源：LeetCode 题目《克隆图》
• 题目链接：克隆图

核心疑问 #

在给出的C++ BFS实现代码中，执行mp[node] = first语句时，我们将原始节点映射到了一个邻接vector为空的新创建克隆节点，为何后续在for(auto adj: curr->neighbors)循环中仍可以正常访问节点的邻接节点？执行mp[node] = first操作是否不会修改原始node指针的引用指向？

对应实现代码 #

/*
// 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 {
public:
    unordered_map<Node* , Node*> mp; 
    
    Node* cloneGraph(Node* node) {
        if(node == NULL) 
        {
            return NULL;
        }
        
        Node* first = new Node(node->val, {}); 
        mp[node] = first;
        
        queue<Node*> q; 
        q.push(node); 
        
        while(q.empty() == false) 
        {
            Node* curr = q.front(); 
            q.pop(); 
            
            for(auto adj: curr->neighbors) 
            {
                if(mp.find(adj) == mp.end()) 
                {
                    mp[adj] = new Node(adj->val, {}); 
                    q.push(adj); 
                    
                }
                
                mp[curr]->neighbors.push_back(mp[adj]); 
            }
        }
        
        return mp[node];
    }
};

解答 #

首先明确结论：mp[node] = first 完全不会修改原始node指针的指向，也不会改动原始节点的任何内容。

• 这里的mp是存储「原始节点指针 -> 对应克隆节点指针」映射关系的哈希表，插入键值对的操作只是在哈希表自身的内存空间里记录两个指针的对应关系，既不会修改原始指针本身存储的地址值，也不会读写原始指针指向的Node对象内存，自然不会改动原始节点保存的neighbors邻接表。
• 整个BFS遍历过程中，队列里存储的始终是原始图的节点指针，从来没有将克隆节点入队：初始化时入队的是传入的原始node指针，每次出队拿到的curr也都是原始节点指针，访问curr->neighbors读取的是原始节点自身存储的邻接表数据，和克隆节点初始状态下邻接表为空没有任何关系。
• 克隆节点的邻接表是单独维护的：遍历到原始节点curr的邻接原始节点adj后，代码会通过mp[adj]拿到adj对应的克隆节点，再将这个克隆节点追加到mp[curr]（也就是curr对应的克隆节点）的邻接表中，这部分操作修改的全是新创建的克隆节点的内存，完全不会触碰原始图的任何节点数据。

内容的提问来源于stack exchange，提问作者utu mutu