[数据结构与算法]【每日一题】力扣133 克隆图

题目

题目链接：133：克隆图

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

示例 4：

输入：adjList = [[2],[1]]
输出：[[2],[1]]

提示：

1. 节点数不超过 100 。
2. 每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
3. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
4. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
5. 图是连通图，你可以从给定节点访问到所有节点。

解题思路

题目着重强调是深度克隆，不是表面的值的复制或引用，所以需要手动申请内存空间。

👉递归

因为要复制的是一个图，所以在循环复制的过程一定会出现死循环的情况，这里就要用一个标记数组对每次遍历过的节点进行标记。这个数组不应该是 int 型或 bool型，应该和节点是一个类型的，具体原因后面解释。

由于题目每个节点都有一个邻居集，所以递归里一定会有一个循环用来遍历邻居集，下面开始思考具体的代码实现。

首先，递归的结束条件是什么？

正常这种题都是，节点为空的时候。

递归函数的参数和类型是什么？

仔细思考会发现，对于图里的每个节点，其节点的值和创建节点只要一行代码就行，但节点的邻居集是需要遍历的，而且邻居集里又对应了图里的其他节点。所以主要是邻居集不好创建，那我们可以在创建邻居集时，递归到邻居集里的节点，只要该节点创建好了直接返回到邻居集就行了。所以函数的类型就是节点类型，创建节点不需要其他的参数，这里就可以直接使用已给出的函数。

函数里的具体内容是什么？

递归结束的条件放在最开始，这是固定的。当节点为空时，应该返回空节点，这是题目的样例。为了防止陷入死循环，当节点已经访问过了，应该返回的是当前节点。原因：

比如样例一，当访问到第三个节点的邻居集时，会发现邻居集里的节点 2 已经访问过了，此时应该返回节点 2 ，才能把节点 2 放到邻居集里。但是返回的节点必须是自己创建的，否则就是引用的节点。这样就可以解释为什么标记数组要和节点类型一样了。

解决了返回问题后，就可以创建节点，然后标记节点和访问节点的邻居集了。

👉迭代

迭代做法同样要一个标记数组，但是比递归多了一个队列。这里标记数组换成哈希表，因为哈希表的查找更方便一点。队列里存放需要克隆的图的节点，其实和层次遍历差不多。如下图：

首先把第一个节点放入队列，然后进入 while 循环，把队列的值弹出。进入 for 循环，循环遍历弹出节点的邻居集。判断邻居集里的节点是否访问过，如果访问过像递归那样把创建过的同样节点放入新创建的邻居集。如果没有访问过，就创建一个同样的新节点，同时把原节点放入队列中。

递归和迭代的区别（官方图解）：

代码（C++）

递归

class Solution {
public:
    Node *vis[105];
    Node* cloneGraph(Node* node) {
        if (!node)
            return node;
        if (vis[node->val])
            return vis[node->val];
        Node *root = new Node(node->val);
        vis[node->val] = root;
        for (int i = 0; i < node->neighbors.size(); ++ i) {
            root->neighbors.push_back(cloneGraph(node->neighbors[i]));
        }
        return root;
    }
};

迭代

这里我放官方有注释的。

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 n = Q.front();
            Q.pop();
            // 遍历该节点的邻居
            for (auto& neighbor: n->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    // 如果没有被访问过，就克隆并存储在哈希表中
                    visited[neighbor] = new Node(neighbor->val);
                    // 将邻居节点加入队列中
                    Q.push(neighbor);
                }
                // 更新当前节点的邻居列表
                visited[n]->neighbors.emplace_back(visited[neighbor]);
            }
        }

        return visited[node];
    }
};

总结

无论是哪种方法都少不了节点的标记，这也算是图的一个特点吧。这种深度复制的方法需要掌握，这可以应用到很多地方，无论是做题还是项目上。

递归函数里的第二个返回值难想到，以及返回的值可以直接放入邻居集里也不好想。

迭代的循环过程也不好想，尤其是使用哈希存储新创建的节点和标记节点的用法不容易想到。