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)