Clone Graph

133. 克隆图

分析

哈希表存储原节点与克隆节点的映射：
- 使用 hash 保存原图节点到克隆节点的映射关系，用于快速找到已克隆的节点，避免重复克隆
DFS 遍历图的所有节点：
- 对每个未访问过的节点，创建其克隆节点并存入 hash
- 遍历当前节点的所有邻居，如果邻居未被克隆，则递归处理
复制邻接关系：
- 遍历所有节点（已在 hash 中），将每个原节点的邻居对应的克隆节点添加到克隆节点的邻居列表中
最终返回起始节点的克隆版本，即为完整的深拷贝图

时间复杂度

图的所有节点和边都会被访问一次，因此时间复杂度为 O(N + E)，其中 N 是节点数，E 是边数

空间复杂度

递归调用栈的深度取决于图的结构，最坏情况下为 O(N)，加上哈希表的存储空间，总体复杂度为 O(N)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


class Solution
{
public:
    Node* cloneGraph(Node* node)
    {
        if (!node)
            return nullptr;

        std::unordered_map<Node*, Node*> hash; // 哈希表存储节点映射
        dfs(node, hash); // 深度优先搜索创建克隆节点

        // 第二次遍历复制邻接关系
        for (auto& [origin, copy] : hash)
            for (Node* neighbor : origin->neighbors)
                copy->neighbors.push_back(hash[neighbor]); // 将原节点的邻接点的克隆节点添加到克隆节点的邻接表中

        return hash[node]; // 返回克隆图的起点
    }

    void dfs(Node* node, std::unordered_map<Node*, Node*>& hash)
    {
        // 克隆当前节点
        hash[node] = new Node(node->val);

        // 递归克隆邻居节点
        for (Node* neighbor : node->neighbors)
            if (hash.count(neighbor) == 0) // 如果邻居未被克隆
                dfs(neighbor, hash); // 递归处理
    }
};