Skip to main content

133. Clone Graph - LeetCode

from collections import deque


# 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 Solution1:
def cloneGraph(self, node: 'Node') -> 'Node':
visited = {}

def dfs(node):
if node in visited:
return visited[node]
visited[node] = Node(val=node.val)
# note: create new node first, then update the neighbors
visited[node].neighbors = [dfs(x) for x in node.neighbors]
return visited[node]

return node and dfs(node)


class Solution2:
def cloneGraph(self, node: 'Node') -> 'Node':
def bfs(node):
visited = {node: Node(val=node.val)}
queue = [node]
while queue:
next_ = []
for q in queue:
for n in q.neighbors:
if n not in visited:
visited[n] = Node(val=n.val)
next_.append(n)
visited[q].neighbors.append(visited[n])
queue = next_
return visited[node]

return node and bfs(node)


class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
def bfs(node):
visited = {node: Node(val=node.val)}
queue = deque([node])
while queue:
q = queue.popleft()
for n in q.neighbors:
if n not in visited:
visited[n] = Node(val=n.val)
queue.append(n)
visited[q].neighbors.append(visited[n])
return visited[node]

return node and bfs(node)