原題

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

注意點：

例子:

輸入:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

輸出:

       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) 來獲得相關源碼。