題目出處
難度
medium
題目分類
Hash Table, Depth-First Search, Breadth-First Search, Graph Theory
2026-09-29 二刷
個人範例程式碼 - 二刷 (2026/09/29)
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
from typing import Optional
class Solution:
def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:
if not node:
return node
visited = {} # key: origin node / value: clone node
# each dfs will clone single
# (and if neighbors not cloned, clone the neighbors first)
def dfs(n):
if n in visited:
return visited[n]
clone = Node(n.val) # clone new node
visited[n] = clone # pair the origin to new node
for neighbor in n.neighbors:
clone.neighbors.append(dfs(neighbor)) # clone the neighbors (if not exist, create it)
return clone
return dfs(node)
算法說明
graph 的經典題型，目前我覺得還不夠熟悉架構，還需要多練練。
- 主要需要 clone node，並建立一個 visited dict 同時負責存已經建立的 clone node，與查詢「舊 -> 新」的配對
- 使用 dfs 來進行解題，一次的 dfs 就是處理好一個 clone node 與對應的 neighbors
- 你可能會想問，如果 neighbors clone node 還沒產生怎麼辦? 透過掃鄰居的過程，會優先把鄰居也建立好，
追到最深沒有新的 visited (clone node 都已經初步產生) 才開始一層一層 return 並把鄰居關係 (Edge) 建立好。
Time Complexity
O(V+E)
V: 查 visited 的時間
E: 內層的 for neighbors 的時間
你可能會想問 dfs 遞迴沒有時間嗎? 基本上沒有 只是跑建立一個 node 的過程，而且大部分已經建立了 (在 visited) 就 return
Space Complexity
O(V)
V: visited 的存放空間
2022-04-16 一刷
個人範例程式碼 - 一刷 (2022/04/16)
"""
# Definition for a Node.
class Node:
def __init__(self, val = 0, neighbors = None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
"""
class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
root = node
if node is None:
return node
# traverse, get all nodes by BFS
old_nodes = self.get_all_nodes(node)
# print(len(nodes))
# clone all nodes
mapping = {}
for old_node in old_nodes:
mapping[old_node] = Node(old_node.val)
# clone all edges
for old_node in old_nodes: #
new_node = mapping[old_node]
for neighbor in old_node.neighbors:
new_neighbor = mapping[neighbor]
new_node.neighbors.append(new_neighbor)
return mapping[root]
def get_all_nodes(self, node):
queue = [node]
result = set([node])
while queue:
head = queue.pop(0)
for neighbor in head.neighbors:
if neighbor not in result:
result.add(neighbor)
queue.append(neighbor)
return result
算法說明
不好處理的題目，題目本身不難，但基本上可以視為 Graph 的基本操作題型。
我們分成三大步驟
- - 找到所有的點，透過 BFS traverse
- 複製所有的點
- 複製所有的邊
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
處理 input 為空的情況，這裡我是直接回傳 node。
Boundary conditions
注意 BFS 的結束條件：
- 當 queue 為空，所有的點都為 visited