Clone Graph (Microsoft Medium) - 面试真题解析

📝

Problem Description (题目描述)

Question Details

给定一个图的数据结构，其中每个 Vertex 包含自己的 data 和一个 neighbors 列表，同时由 Graph 作为容器保存所有顶点。要求实现一个 clone 函数，对输入图进行完全独立的深拷贝，返回一个与原图结构和值相同、但所有顶点对象均为新创建对象的图副本。克隆后的图不能与原图共享任何 Vertex 对象或邻居列表，并且需要正确处理图中的环、重复边以及多个顶点指向同一个邻居的情况。

🔍

Example (输入输出示例)

Test Cases

示例 1：

输入：

1 -- 2
|    |
4 -- 3

输出：

1' -- 2'
|     |
4' -- 3'

解释：

原图包含 1、2、3、4 四个顶点。
克隆后需要创建四个完全独立的新顶点 1'、2'、3'、4'。
新图中的连接关系必须与原图完全一致。
修改原图中的任意顶点或邻居关系，都不能影响克隆图。

示例 2：

输入：

1 -> 2
2 -> 1

输出：

1' -> 2'
2' -> 1'

解释：

原图中存在环 1 -> 2 -> 1。
DFS 遍历到 1 后创建 1'，再遍历到 2 创建 2'。
当再次从 2 访问 1 时，1 已经存在于 clone_map 中，因此直接复用 1'。
这样既可以保持原图结构，又可以避免无限递归。

示例 3：

输入：

Graph = []

输出：

[]

解释：

如果输入图为空，则不存在需要克隆的顶点。
可以直接返回空图。

💡

Approach (核心思维推导与最优策略)

Optimal Strategy

核心思想
- 使用 DFS 沿着图的 edges 真正遍历整个图，而不是简单遍历 Graph.vertices 数组。
- 使用哈希表 clone_map 建立“原始顶点 -> 克隆顶点”的映射。
- 每次第一次访问一个原始 Vertex 时，立即创建对应的克隆对象并放入 clone_map。
- 随后递归处理它的所有 neighbors，将对应的克隆顶点加入当前克隆顶点的邻居列表。
- 哈希表不仅用于避免重复创建顶点，也是处理环形图的关键。
关键观察/数学性质
- 图可能包含环，因此不能单纯递归访问邻居，否则可能无限循环。
- 一个原始顶点必须始终对应唯一的克隆顶点，因此可以使用 clone_map[original] = clone 保证对象一一对应。
- 必须在递归访问邻居之前先将当前顶点加入 clone_map，这样遇到环时可以立即返回已经创建的克隆节点。
- 如果图中多个顶点都指向同一个节点，那么这些边必须最终指向同一个克隆节点，而不能重复创建多个副本。
算法步骤
- 如果输入图为空，直接返回空结果。
- 创建空的 clone_map。
- 从图中的一个入口顶点开始执行 DFS。
- 如果当前原始顶点已经存在于 clone_map，直接返回对应的克隆顶点。
- 如果当前顶点尚未被访问，则创建一个新的克隆顶点。
- 立即将原始顶点和克隆顶点加入 clone_map。
- 遍历当前顶点的所有 neighbors。
- 对每个邻居递归调用 DFS，并将返回的克隆邻居加入当前克隆顶点。
- DFS 完成后返回入口顶点对应的克隆图。
边界条件与特殊情况
- 输入图为空时返回空图。
- 图只有一个顶点时，需要创建一个新的独立顶点。
- 顶点存在自环时，需要确保自环连接到克隆顶点自身。
- 图中存在环时，必须依赖 clone_map 防止无限递归。
- 多条边指向同一个顶点时，所有对应边应该指向同一个克隆对象。
- 如果 Graph 容器保存多个互不连通的 connected components，则需要从所有尚未克隆的顶点分别执行 DFS，而不能只从单个入口开始。
Follow-up / 优化讨论
- 如果面试官要求去掉 helper function，可以将 DFS 逻辑直接写入主函数，或者使用显式 Stack 实现迭代 DFS。
- 如果图非常深，递归 DFS 可能产生 O(V) 的调用栈，因此工程环境中可以考虑使用迭代 DFS。
- 如果 Graph 本身保存所有 vertices，则可以遍历 Graph.vertices，对每个尚未存在于 clone_map 的顶点启动一次 DFS，从而覆盖多个 disconnected components。
- 面试中需要注意“遍历顶点数组”和“图 DFS”是两个不同概念。如果声称使用 DFS，就必须沿着 neighbors / edges 进行图结构遍历。

Time Complexity (时间复杂度)

时间复杂度：O(V + E)，其中 V 为顶点数量，E 为边数量。
每个顶点最多创建和访问一次，每条边最多处理一次。

Space Complexity (空间复杂度)

辅助空间：O(V)。
clone_map 需要保存每个原始顶点与克隆顶点之间的映射。
递归 DFS 的最坏调用栈深度为 O(V)。
不计输出图本身的空间。

Solution (Python 3 最优解)

Python 3 Solution

from typing import Optional
class Vertex:
    def __init__(self, data: int):
        self.data = data
        self.neighbors = []
class Graph:
    def __init__(self, vertices=None):
        self.vertices = vertices if vertices is not None else []
class Solution:
    def cloneGraph(self, graph: Graph) -> Graph:
        # 空图没有任何顶点需要复制，因此直接返回一个空 Graph。
        if not graph.vertices:
            return Graph([])
        # clone_map 保存“原始 Vertex -> 克隆 Vertex”的一一对应关系。
        # 它有两个作用：
        # 1. 防止同一个原始顶点被重复创建多个克隆对象。
        # 2. 遇到环时可以直接返回已经创建的克隆对象，避免无限递归。
        clone_map = {}
        def dfs(original: Vertex) -> Vertex:
            # 如果这个顶点已经被克隆过，直接返回之前创建的对象。
            # 例如存在 1 -> 2 -> 1 的环时，第二次访问 1 就会走到这里。
            if original in clone_map:
                return clone_map[original]
            # 第一次遇到当前顶点时，创建一个全新的 Vertex。
            # 此时只复制 data，neighbors 会在下面的 DFS 中逐步建立。
            clone = Vertex(original.data)
            # 必须在递归处理 neighbors 之前保存映射。
            # 这样即使后面的边形成环，也能找到当前已经创建好的 clone。
            clone_map[original] = clone
            # 真正的 DFS 图遍历发生在这里：
            # 我们沿着 original.neighbors 的边访问其他顶点，
            # 而不是简单遍历 Graph.vertices 数组。
            for neighbor in original.neighbors:
                # 递归获得 neighbor 对应的克隆节点。
                # 如果 neighbor 已经被访问过，dfs 会直接返回已有 clone。
                cloned_neighbor = dfs(neighbor)
                # 将克隆后的邻居连接到当前克隆顶点。
                clone.neighbors.append(cloned_neighbor)
            # 当前顶点以及它能够到达的邻居都已经完成克隆。
            return clone
        # 从 Graph 中的第一个顶点开始 DFS。
        # 对于单个 connected component，这次 DFS 可以访问整个图。
        first_clone = dfs(graph.vertices[0])
        # 如果题目保证 Graph 是连通图，可以直接返回第一个克隆顶点所在的图。
        # 如果 Graph 允许 disconnected components，则下面需要额外处理其他 vertices。
        cloned_vertices = []
        for original in graph.vertices:
            # 如果当前原始顶点已经被 DFS 访问过，直接复用对应 clone。
            # 否则从它重新启动 DFS，以覆盖 disconnected component。
            if original in clone_map:
                cloned_vertices.append(clone_map[original])
            else:
                cloned_vertices.append(dfs(original))
        # Graph 容器保存所有克隆后的顶点，
        # 每个顶点内部的 neighbors 已经通过 DFS 建立完成。
        return Graph(cloned_vertices)

LeetCode 相似题目推荐与延伸练习

掌握同类考点的变体套路与最优解模板，举一反三快速拿下技术面试：

⚡133. Clone Graph

⚡138. Copy List with Random Pointer

⚡1490. Clone N-ary Tree

⚡146. LRU Cache

Clone Graph