133.clone-graph.md

133. 克隆图

1. 描述

   • 对于无向的连通 图，给你一个节点的引用，请你返回该图的 深拷贝（克隆）。
   • 提示：
     • 每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
     • 由于图是无向的👇
       • 如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
       • 无向图是一个简单图，没有重复的边，也没有自环。
     • 图是连通图，你可以从给定节点访问到所有节点。
   • 定义

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

2. 思路

   • 由于：每个 Node.val ∈【1，100】，且每个 Node.val 唯一。
     • 定义unordered_map<int, Node*> visit_clone
     • visit[Node.val, cloneNode] 表示 Node 节点已被访问，且cloneNode 是 Node 对应的克隆节点
   • DFS
   • BFS

3. 实现

   • DFS

     class Solution {
     public:
         unordered_map<int, Node*>visit_clone;
         Node* dfs(Node* node){
             if(!node)
                 return node;
             // 如果已访问，直接返回克隆节点
             if(visit_clone.count(node->val))
                 return visit_clone[node->val];
             // 如果没访问，标记访问，并且克隆节点
             visit_clone[node->val] = new Node(node->val);
             // 克隆邻居节点
             for(auto n: node->neighbors){
                 // DFS 递归
                 visit_clone[node->val]->neighbors.push_back( dfs(n) );
             }
             return visit_clone[node->val];
         }
         Node* cloneGraph(Node* node) {
             return dfs(node);
         }
     };
     

   • BFS

     class Solution {
     public:
         Node* cloneGraph(Node* node) {
             if(!node)
                 return node;
             unordered_map<int, Node*>visit_cloneNode;
             // 队列里，是克隆之前的节点
             queue<Node*>Q;
             Q.push(node);
             visit_cloneNode[node->val] = new Node(node->val);
             Node* cur;
             while(!Q.empty()){
                 cur = Q.front();
                 Q.pop();
                 // 克隆邻居节点
                 for(auto n: cur->neighbors){
                     // 如果没有访问，标记为访问，并且克隆 邻居节点
                     if(!visit_cloneNode.count(n->val)){
                         Q.push(n);
                         visit_cloneNode[n->val] = new Node(n->val);
                     }                
                     visit_cloneNode[cur->val]->neighbors.push_back(visit_cloneNode[n->val]);                
                 }
             }
             return visit_cloneNode[node->val];
         }
     };