Python solution with detailed explanation

  • 0


    Clone Graph

    Breadth First Based Solution

    • Add to cache (if not present) when you first visit a neighbor and then enqueue.
    • Always add the neighbor links while graph traversal.
    from collections import deque    
    class Solution:
        # @param node, a undirected graph node
        # @return a undirected graph node
        def cloneGraph(self, node):
            if node is None:
                return None
            dq = deque()
            cache = {node:UndirectedGraphNode(node.label)}
            while len(dq):
                for _ in range(len(dq)):
                    x = dq.popleft()
                    for nbr in x.neighbors:
                        if nbr not in cache:
                            cache[nbr] = UndirectedGraphNode(nbr.label)
            return cache[node]

    Depth First based copy

    • Simple recursive algorithm to copy with a dictionary
    class Solution:
        def helper(self, node, cache):
            if node is None:
                return None
            elif node in cache:
                return cache[node]
                cache[node] = UndirectedGraphNode(node.label)
                for x in node.neighbors:
                    cache[node].neighbors.append(self.helper(x, cache))
                return cache[node]

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.