克隆图

难度: Medium

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

图中的每个节点都包含它的值 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]]

提示：

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

Submission

运行时间: 23 ms

内存: 16.4 MB

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if node is None:
            return None

        records = dict()

        def get_new_node(u):
            if u.val in records:
                return records[u.val]
            else:
                n = Node(u.val)
                records[u.val] = n
                return n

        new_node = get_new_node(node)
        q = deque()
        q.append(node)
        visited = [False]*101
        visited[node.val] = True
        while len(q) > 0:
            u = q.popleft()
            new_u = get_new_node(u)
            for v in u.neighbors:
                new_u.neighbors.append(get_new_node(v))
                if not visited[v.val]:
                    visited[v.val] = True
                    q.append(v)
        return new_node

Explain

这个题解使用了广度优先搜索（BFS）的思路来克隆图。首先判断给定的节点是否为空，如果为空则直接返回None。然后使用一个字典records来记录原始节点和克隆节点之间的映射关系，避免重复创建节点。定义一个辅助函数get_new_node(u)，用于根据原始节点u创建对应的克隆节点，并将其存储在records中。接下来，从给定的节点开始进行BFS遍历，使用一个队列q存储待遍历的节点，并用一个布尔数组visited标记节点是否已被访问过。在BFS的过程中，对于每个遍历到的节点u，通过get_new_node(u)获取其对应的克隆节点new_u，然后遍历u的所有邻居节点v，通过get_new_node(v)获取v的克隆节点并将其添加到new_u的邻居列表中。如果v尚未被访问过，则将其标记为已访问，并将其加入队列q中等待遍历。最后，返回给定节点对应的克隆节点作为结果。

时间复杂度: O(n+m)，最坏情况下为O(n^2)

空间复杂度: O(n)

class Solution:
    def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
        if node is None:
            return None
        
        records = dict()  # 记录原始节点和克隆节点的映射关系
        
        def get_new_node(u):  # 辅助函数，根据原始节点创建克隆节点
            if u.val in records:
                return records[u.val]
            else:
                n = Node(u.val)
                records[u.val] = n
                return n
        
        new_node = get_new_node(node)  # 创建给定节点的克隆节点
        q = deque()  # BFS使用的队列
        q.append(node)  # 将给定节点加入队列
        visited = [False]*101  # 标记节点是否已访问
        visited[node.val] = True  # 标记给定节点为已访问
        
        while len(q) > 0:
            u = q.popleft()  # 取出队首节点
            new_u = get_new_node(u)  # 获取该节点的克隆节点
            
            for v in u.neighbors:  # 遍历该节点的所有邻居
                new_u.neighbors.append(get_new_node(v))  # 将邻居的克隆节点添加到克隆节点的邻居列表中
                
                if not visited[v.val]:  # 如果该邻居节点尚未被访问
                    visited[v.val] = True  # 标记为已访问
                    q.append(v)  # 将该邻居节点加入队列
        
        return new_node  # 返回给定节点的克隆节点作为结果

Explore

在编程中，进行空值检查是一种常见的做法，旨在防止运行时错误。在图的克隆问题中，如果给定的节点为空，那么没有任何节点可以克隆，因此函数应该返回None。这不仅防止了后续代码对空值进行操作导致的错误，也正确地反映了输入数据的状态，即一个空图没有任何内容可被克隆。

在这种情况下，使用节点的值作为键来创建映射主要是因为值是唯一的且易于比较的标识符。使用节点对象本身作为键虽然理论上可行，但在实际操作中可能会更复杂，因为需要确保对象的唯一性和一致性。此外，使用值作为键可以更直观地访问和检查映射关系，尤其是在调试和维护代码时。

是的，该过程确保了原图中任意两个相邻节点在克隆图中也将相邻。通过对每个节点使用get_new_node函数来获取或创建克隆节点，并将这些克隆节点添加到对应的克隆邻居列表中，保证了克隆图中节点间的连接关系与原图一致。通过这样的方法，任何在原图中相邻的两个节点，其对应的克隆节点也会在克隆图中成为邻居。

是的，当前代码中visited数组固定为101，意味着它只能处理节点值从0到100的图。如果需要处理更大的图，可以考虑以下几种方法：1. 如果节点数和节点值范围是已知的，可以将visited数组的大小调整为节点值的最大范围加一。2. 如果节点值的范围未知或非常大，可以使用哈希表（例如Python中的字典）来代替数组，以节点值为键，访问状态为值，这样可以灵活地处理任意范围的节点值。