LeetCode - Clone Graph（圖的克隆）

題目描述

給定一個無向連通圖的引用，請你返回該圖的深拷貝（克隆）。圖中的每個節點包含一個唯一的值 val 和一個列表 neighbors，表示與其相鄰的節點。

例子：

輸入：adjList = [[2,4],[1,3],[2,4],[1,3]]
輸出：[[2,4],[1,3],[2,4],[1,3]]
解釋：
1 -- 2
|    |
4 -- 3
原圖表示一個四個節點的無向連通圖，其中每個節點的 `val` 分別為 1, 2, 3, 和 4。
返回的應該是該圖的深拷貝，其結構和節點連接方式應與原圖相同。

解法思路

這個問題的核心是創建一個圖的深拷貝，即創建新節點和原節點具有相同的結構和連接，但不是直接引用原節點。

方法：深度優先搜索（DFS） 或 廣度優先搜索（BFS）

可以使用深度優先搜索（DFS）或廣度優先搜索（BFS）來遍歷圖，同時克隆每個節點。

1. 字典記錄節點映射：用一個字典 cloned_nodes 存儲已克隆的節點，以避免重複克隆和循環引用。鍵為原節點，值為克隆後的節點。

2. DFS/BFS 克隆圖：
   • 如果節點已經克隆過，直接返回克隆節點。
   • 否則，創建一個新的節點，並將其添加到 cloned_nodes。
   • 遍歷當前節點的相鄰節點並遞歸克隆，將克隆後的相鄰節點添加到新節點的 neighbors 列表中。
3. 返回克隆後的起始節點：最終返回克隆圖的起始節點。

範例代碼

以下是使用 DFS 的 Python 實現：

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node:
        return None

    # 使用字典記錄克隆的節點
    cloned_nodes = {}

    def dfs(node):
        # 如果節點已經克隆過，直接返回克隆的節點
        if node in cloned_nodes:
            return cloned_nodes[node]
        
        # 克隆當前節點（僅複製值，不複製鄰居）
        clone = Node(node.val)
        cloned_nodes[node] = clone
        
        # 克隆鄰居節點並加入新節點的鄰居列表
        for neighbor in node.neighbors:
            clone.neighbors.append(dfs(neighbor))
        
        return clone

    return dfs(node)

代碼解析

1. cloned_nodes 字典：記錄已經克隆過的節點，以避免重複克隆。
2. DFS 函數：每次調用時，檢查當前節點是否已克隆。
   • 若未克隆，創建新的節點並遞歸克隆其鄰居，將克隆的鄰居添加到新節點的 neighbors 列表中。
3. 返回結果：返回克隆後的整個圖的起始節點。

時間和空間複雜度

• 時間複雜度：O(N)，其中 N 是圖中節點的數量。每個節點僅訪問一次。
• 空間複雜度：O(N)，由於遞歸棧和 cloned_nodes 字典需要額外空間。