Leetcode 133。具有dfs理解的克隆图

Question

嗨，我理解dfs有问题。我知道DFS有两个版本；我们在通话前和通话后标记访问

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)

然而，当我将version1（调用之前访问过的标记）应用于问题（https://leetcode.com/problems/clone-graph/）时，它抱怨并且没有复制

这是我的解决方案：

"""
# 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)

让我知道为什么会有问题。我不明白为什么它不起作用

Answer 1

代码无法工作的主要原因是将原始节点存储在visited字典中。必须将已处理的节点DFS克隆存储在visited中。为什么？因为在new_neighbors.append(visited[nei.val])内，您将访问的节点添加到新克隆节点的邻居。但任何克隆节点都应该只有克隆的邻居，而不是原始节点

我决定使用DFS实现您的算法/想法的我自己的版本，下一个代码被LeetCode系统成功接受（所有测试通过）：

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

Answer 2

我们使用散列映射创建从原始节点到复制节点的映射。然后，我们使用哈希映射来检查我们是否在之前访问了节点

  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