【LeetCode】133.克隆图
本题的一个难点是：
1. 题目
这是一道很好的题目，至少把目前的我给困住了。
2. 分析
我的思路是深度搜索，深搜的同时记录上一次访问的节点（也就是当前节点的父节点）是什么。然后记录一个节点关系即可，代码如下：
"""
# Definition for a Node.
class Node:def __init__(self, val = 0, neighbors = None):self.val = valself.neighbors = neighbors if neighbors is not None else []
"""from typing import Optional
class Solution:def cloneGraph(self, node: Optional['Node']) -> Optional['Node']:vis = set() # 正在访问的节点pre = Noneroot = self.dfs(pre, node, vis)print(root.val)return rootdef dfs(self, pre, cur, vis):print("1",cur.val)node = Node()if cur:vis.add(cur.val)node.val = cur.valelse:returnif pre :pre.neighbors.append(node)node.neighbors.append(pre)# 找出所有的邻居节点for nei in cur.neighbors:print("2",nei.val)if nei.val not in vis:self.dfs(node, nei, vis)return node
上面这版代码存在的一个问题是：就是存在漏访问的情况。也就是如下这两行红框中的代码导致：
例如在样例：[[2,4],[1,3],[2,4],[1,3]]中（对应的图是如下所示），
这版代码就会造成1<=>4 的漏访问。更深层次的原因是：这版代码是在深搜的时候clone对应的节点，但如果没深搜到这个节点，就没法clone这个邻居，而vis数组导致不会深搜到这个节点，从而产生遗漏。
3. 代码
我看了一下官方题解，代码写的确实比我好。官方题解的思想就是：使用一个哈希表存储某个节点被clone的节点。如果某节点没有被clone过，那么继续深搜；如果有，那么及时返回。在深搜的过程中维护好邻居关系即可。