Python solution with detailed explanation


  • 0
    G

    Solution

    Clone Graph https://leetcode.com/problems/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()
            dq.append(node)
            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)
                            dq.append(nbr)
                        cache[x].neighbors.append(cache[nbr])
            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]
            else:
                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.