Leetcode 133. Clone Graph with dfs understanding

Question

Hi I have a problem understanding dfs. What I know is DFS has two versions; we mark visited before call and after call.

def solution1(start):
  def dfs1(cur):
    for nei in cur.neighbors:
      if nei not in visited:
        ## mark visit before call
        visited.add(nei)
        dfs1(nei)
  ## drive dfs1
  visited = set()
  visited.add(start)
  dfs1(start)

def solution2(start):
  def dfs2(cur):
    ## mark visit after call
    visited.add(cur)
    for nei in cur.neighbors:
      if nei not in visited:
        dfs2(nei)
  ## drive dfs2
  dfs2(start)

However, when I applied version1 (mark visited before a call) to the problem(https://leetcode.com/problems/clone-graph/), it complained and did not copy.

This is my solution:

"""
# 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 Solution:
    """
    def dfs1(cur):
        for nei in cur.neighbors:
            if nei in visited: continue
            visited.add(nei)
            dfs1(nei)
    visited.add(start_node)
    dfs1(start_node)
    """
    def dfs(self, cur, visited):
        
        new_node = Node(cur.val)
        # visited[cur.val] = new_node
        new_neighbors = []
        for nei in cur.neighbors:
            if nei.val not in visited:
                visited[nei.val] = nei
                new_neighbors.append(self.dfs(nei, visited))
            else:
                new_neighbors.append(visited[nei.val])
                
        new_node.neighbors = new_neighbors
        return new_node
        
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node == None:
            return None
        visited = {}
        
        visited[node.val] = node
        return self.dfs(node, visited)

Let me know why this has problem. I don't understand why it does not work.

user_941531 · Answer

Main reason that your code doesn't work is because you store original node inside visited dictionary. You have to store processed DFS clone of a node inside visited. Why? Because inside new_neighbors.append(visited[nei.val]) you add visited node to neighbours of new cloned node. But any cloned node should have only cloned neighbours, not originals.

I decided to implement my own version of your algorithm/idea using DFS, next code is successfully accepted by LeetCode system (all tests pass):

class Solution:
    def __init__(self):
        self.visited = {}
    def cloneGraph(self, node: 'Node') -> 'Node':
        if node is None:
            return None
        if node.val in self.visited:
            return self.visited[node.val]
        nnode = Node(val = node.val)
        self.visited[nnode.val] = nnode
        nnode.neighbors = [self.cloneGraph(c) for c in node.neighbors]
        return nnode

user_10262805 · Answer

We use the hash map to create a map from original nodes to copied nodes. Then we use the hash map to check if we visit the node before or not.

  def cloneGraph(self,node):  
       # I used closure instead of passing this object
        visited={}

        def dfs(node):
            if node in visited:
                # this returned value will be used inside for loop copy.neighbors.append(dfs(nei))
                return visited[node]
            #if node is not in visited we add it
            # this is the first part of the copy. first copy the val
            copy=Node(node.val)
            visited[node]=copy
            # we create the neighbors array of "copy" node
            for nei in node.neighbors:
                copy.neighbors.append(dfs(nei))
            return copy
        return dfs(node) if node else None

Leetcode 133. Clone Graph with dfs understanding

2 Answers