Clone Graph

Graph
Medium

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def cloneGraph(self, originalNode):
        if not originalNode:
            return

        cloneOfNode = Node(originalNode.val)

        clonedNodes = {originalNode: cloneOfNode}

        self.bfs(originalNode, clonedNodes)

        return cloneOfNode

    def bfs(self, startingNode, clonedNodes):
        queue = deque([startingNode])

        while queue:
            originalNode = queue.popleft()

            for originalNeighbor in originalNode.neighbors:
                isCloned = originalNeighbor in clonedNodes

                if isCloned:
                    cloneOfNeighbor = clonedNodes[originalNeighbor]
                    clonedNodes[originalNode].neighbors.append(cloneOfNeighbor)
                    continue

                cloneOfNeighbor = Node(originalNeighbor.val)
                clonedNodes[originalNeighbor] = cloneOfNeighbor
                clonedNodes[originalNode].neighbors.append(cloneOfNeighbor)

                queue.append(originalNeighbor)

Learn

#Breadth-First Search

Videos