Skip to main content

Clone Graph

Question​

Given a reference of a node in a connected undirected graph, how can we clone the graph, including all its nodes and edges?

Example 1
None

Solution​

all//Clone Graph.py


"""
# Definition for a Node.
class Node:
    def __init__(self, val = 0, neighbors = []):
        self.val = val
        self.neighbors = neighbors
"""

# python solution
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None

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

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

        return visited[node]