LeetCode 133. 克隆图

题目描述

给你一个无向连通图中一个节点的引用，请你返回该图的深拷贝。图中的每个节点都包含一个值（int）和一个邻居列表（List[Node]）。

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

测试用例格式：

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

邻接列表是有限集合的 unordered list，用于表示有限图。列表中的每个元素描述了图中节点的邻居集合。

给定的节点将始终是值为 1 的节点。你必须返回给定节点的拷贝，并且不能改变原图。

解题过程

这个问题的核心是创建一个与原图结构完全相同的新图，但所有节点都必须是新创建的（深拷贝）。难点在于处理图中可能存在的环，以及避免重复创建节点。

步骤 1：分析问题与确定方法

1. 深拷贝要求：我们需要创建全新的节点对象，而不是复制引用。
2. 图的结构：图由节点和边组成，每个节点有值和邻居列表。
3. 关键挑战：如何处理已经拷贝过的节点？如果遇到已经拷贝过的节点，我们应该使用之前创建的拷贝，而不是重新创建。
4. 解决方案：使用深度优先搜索（DFS）或广度优先搜索（BFS）遍历原图，同时用一个哈希表（字典）来记录原节点和对应拷贝节点的映射关系。

步骤 2：定义节点类

首先，我们需要定义题目中给出的节点类：

class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}

步骤 3：深度优先搜索（DFS）解法

DFS解法使用递归来遍历图，同时创建新节点。

1. 创建哈希表：使用 HashMap<Node, Node> 来存储原节点到拷贝节点的映射。
2. DFS递归函数：
   • 如果节点为空，返回空
   • 如果节点已经在哈希表中，说明已经拷贝过，直接返回对应的拷贝节点
   • 否则，创建新节点，添加到哈希表
   • 递归地拷贝所有邻居节点
3. 返回结果：返回给定节点对应的拷贝节点

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        
        // 哈希表：原节点 -> 拷贝节点
        Map<Node, Node> visited = new HashMap<>();
        return dfs(node, visited);
    }
    
    private Node dfs(Node node, Map<Node, Node> visited) {
        // 如果节点已经访问过，直接返回对应的拷贝节点
        if (visited.containsKey(node)) {
            return visited.get(node);
        }
        
        // 创建当前节点的拷贝
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);
        
        // 递归拷贝所有邻居节点
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(dfs(neighbor, visited));
        }
        
        return cloneNode;
    }
}

步骤 4：广度优先搜索（BFS）解法

BFS解法使用队列来按层遍历图。

1. 特殊情况处理：如果输入节点为空，返回空
2. 创建哈希表和队列：
   • 哈希表记录原节点到拷贝节点的映射
   • 队列用于BFS遍历
3. 初始节点处理：
   • 创建起始节点的拷贝
   • 将原节点和拷贝节点加入哈希表
   • 将原节点加入队列
4. BFS遍历：
   • 从队列中取出节点
   • 遍历该节点的所有邻居
   • 如果邻居节点还没被拷贝过：
     • 创建拷贝节点
     • 加入哈希表和队列
   • 将邻居的拷贝节点添加到当前拷贝节点的邻居列表中
5. 返回结果：返回起始节点的拷贝

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        
        // 哈希表：原节点 -> 拷贝节点
        Map<Node, Node> visited = new HashMap<>();
        // 队列用于BFS
        Queue<Node> queue = new LinkedList<>();
        
        // 创建起始节点的拷贝
        Node cloneNode = new Node(node.val, new ArrayList<>());
        visited.put(node, cloneNode);
        queue.offer(node);
        
        while (!queue.isEmpty()) {
            Node current = queue.poll();
            
            // 遍历当前节点的所有邻居
            for (Node neighbor : current.neighbors) {
                if (!visited.containsKey(neighbor)) {
                    // 如果邻居节点还没被访问过，创建拷贝并加入哈希表
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    queue.offer(neighbor);
                }
                // 将邻居的拷贝节点添加到当前拷贝节点的邻居列表中
                visited.get(current).neighbors.add(visited.get(neighbor));
            }
        }
        
        return cloneNode;
    }
}

步骤 5：复杂度分析

• 时间复杂度：O(N + M)，其中 N 是节点数，M 是边数。我们需要访问每个节点和每条边一次。
• 空间复杂度：O(N)，哈希表需要存储所有节点的映射关系，递归栈的深度在最坏情况下是 O(N)。

步骤 6：关键要点总结

1. 哈希表的作用：避免重复创建节点和防止循环引用。
2. DFS vs BFS：两种方法都可以解决问题，DFS代码更简洁，BFS在极端情况下（深度很大）可能更稳定。
3. 边界情况：空图、单节点图、有环图都需要正确处理。
4. 深拷贝本质：创建新对象，但保持与原对象相同的结构关系。

这个算法很好地展示了图遍历在解决图相关问题中的应用，特别是如何处理图中的环和避免重复工作。