# 133. Clone Graph

133. Clone Graph

## 廣度優先搜索

"""
# 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':
if not node:
return node

queue = deque([node])
visited = {}
visited[node] = Node(node.val)

while queue:
root = queue.popleft()
for neighbor in root.neighbors:
if neighbor not in visited:
visited[neighbor] = Node(neighbor.val, [])
queue.append(neighbor)
visited[root].neighbors.append(visited[neighbor])

return visited[node]


## 深度優先搜索

"""
# 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':
visited = {}

def dfs(node):
if not node:
return node
if node in visited:
return visited[node]

clone = Node(node.val, [])
visited[node] = clone

if node.neighbors:
clone.neighbors = [dfs(n) for n in node.neighbors]
return clone

return dfs(node)