LeetCode 解題：Clone Graph

原題

對一個無向圖進行複製，圖中每個節點都有自己的標籤和相鄰節點列表。

範例：

輸入：
  1
 / \
/   \
0 --- 2
 \   /
  \_/

輸出：相同結構的新圖

解題思路

因圖中可能存在環，直接複製節點及其鄰居並遞迴操作會陷入死循環。為避免重複訪問，需對已複製節點進行快取。我們用一個以標籤為鍵、節點為值的字典記錄已訪問節點。當透過鄰接關係訪問節點時，若為首次訪問，則加入堆疊繼續訪問其鄰居，並記錄已訪問，同時更新已訪問節點的鄰居列表。當堆疊為空時，所有節點訪問完畢，圖複製成功。

AC 原始碼

# Definition for a undirected graph node
class UndirectedGraphNode(object):
    def __init__(self, x):
        self.label = x
        self.neighbors = []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return node
        visited = {}
        first = UndirectedGraphNode(node.label)
        visited[node.label] = first
        stack = [node]
        while stack:
            top = stack.pop()
            for n in top.neighbors:
                if n.label not in visited:
                    visited[n.label] = UndirectedGraphNode(n.label)
                    stack.append(n)
                visited[top.label].neighbors.append(visited[n.label])
        return first

if __name__ == "__main__":
    None

歡迎查看我的 Python GitHub (https://github.com/gavinfish/LeetCode-Python) 獲取相關原始碼。