# Leetcode 133. Clone Graph

題目給定一個無向簡單圖，要求複製一個一模一樣的圖並返回複製後的圖

複製圖有一個需要注意的地方，節點中的每個鄰居節點中，都需要紀錄下該節點的所有鄰居信息

因此在處理節點時，需要一個哈希表來紀錄已經訪問過的節點

以便其他節點需要的時候，不需要在遍歷一次節點，也避免陷入無窮迴圈中

## DFS 深度優先遍歷

"""
# 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':
        def dfs(node: 'Node', visited):
            cloneNode = Node(node.val) # 當前節點
            visited[node] = cloneNode # 把當前節點加入到已訪問

            for n in node.neighbors: # 遍歷所有相鄰節點
                if n in visited: # 如果前面已經遍歷過，直接拿取以前處理過的資料
                    cloneNode.neighbors.append(visited[n])
                else: # 如果前面沒有遍歷過，開始處理此節點，並把返回節點加入到鄰居節點中
                    cloneNode.neighbors.append(dfs(n,visited))
            return cloneNode
        
        if not node: # 防止空節點
            return node

        return dfs(node,{})

## 參考資料

[LeetCode: 133-Clone Graph 解題思路](https://clay-atlas.com/blog/2022/02/23/leetcode-133-clone-graph/)
[Clone Graph - Depth First Search - Leetcode 133](https://www.youtube.com/watch?v=mQeF6bN8hMk)