133.克隆图

原题

一、dfs

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = {}	#hash存储已访问过的
        def dfs(node):
            if not node:	#防止空图用例
                return None
            if node in visited:		#防止重复访问，遇到访问过的节点，直接返回其拷贝
                return visited[node]
            nodeCpy = Node(node.val)	#拷贝node
            visited[node] = nodeCpy		#hash键为原图节点，值为拷贝节点
            for neighbor in node.neighbors:		#dfs处理node的邻居
                nodeCpy.neighbors.append(dfs(neighbor))
            return nodeCpy
        return dfs(node)

二、bfs

与dfs类似，还是将(原node，复制node)存储在hash中避免重复访问

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node:
            return None
        visited = {}     #存储访问过的
        q = queue.Queue()
        visited[node] = Node(node.val)   #先访问node
        q.put(node)
        while not q.empty():
            size = q.qsize()
            for i in range(size):
                cur = q.get()
                for neighbor in cur.neighbors:
                    if neighbor not in visited:
                        q.put(neighbor)
                        nodeCpy = Node(neighbor.val)
                        visited[neighbor] = nodeCpy
                    visited[cur].neighbors.append(visited[neighbor])
        return visited[node]    #hash存储的值才是复制图