克隆图：哈希表把旧节点映射到新节点
遍历原图时每碰到一个新节点就建一份，立刻写入 map。邻居只连新节点。已经在 map 里的，直接拿出来接边。
DFS 或 BFS 均可。clone(n) 若 n 已在 map 中，返回对应的新节点；否则新建、先放入 map，再对每个邻居递归并把返回值接到新邻居列表。先登记再走邻居，自环和普通环都安全。时间 O(V+E)，空间 O(V)。
给你一张无向连通图里某个节点的引用，返回这张图的深拷贝。深拷贝的意思是：每个节点都是新对象，边也是新列表，拷贝出来的图不能再指回原图的任何节点。
主例四个节点：1 连 2 和 3，2 连 1 和 4，3 连 1 和 4，4 连 2 和 3，是一个方。拷贝之后结构相同，但是 1'、2'、3'、4' 全是新节点。从 1' 出发走一圈，碰不到原来的 1。
无向图有环。本文要回答：没有哈希表为什么会转圈或建出两份同一节点，以及主例里节点 1 的两条边是怎样接到 2' 和 3' 上的。
先克隆节点，再接邻居
深拷贝要两件事同时成立：每个旧节点恰好对应一个新节点；旧边 (u,v) 变成新边 (u',v')。只新建节点、边仍指向旧邻居，那是浅拷贝。每条边都 new 一个邻居，同一节点会在图里出现多份。缺的是一张对照表：旧指针 → 已经建好的新指针。
DFS 走进节点 n。map 里已有 n，说明 n' 建过了，直接返回 n'，不要再建，也不要再顺着 n 的邻居往下走——那条路会在环上转死。map 里没有，就 new 一个值相同、邻居列表为空的节点，立刻写入 map，然后再遍历 n.Neighbors，把 clone(邻居) 的返回值 append 到 n' 的邻居列表。先写入再递归，是为了自环和立刻回头的无向边：邻居走回 n 时，map 已经能交出 n'。
用手走主例，从 1 出发。1 不在表里，建 1'，登记。1 的邻居是 2、3。先走进 2：建 2'，登记，2 的邻居是 1 和 4。clone(1) 命中表，把 1' 接到 2'；再走进 4：建 4'，4 的邻居是 2 和 3。2 已在表里；3 还没有，建 3'，3 的邻居 1、4 都已在表里，接上 1' 和 4'。回到 1，另一个邻居 3 已经在表里，把 3' 接到 1'。四个节点各建一次，四条无向边在新图里各出现两次邻接记录。
演示场景先标出克隆 1，再标出邻居 2 接到 1'，最后 3、4 都在表里。看的就是「旧节点第一次出现时建新的，第二次出现时只取表」。BFS 同样：队列里放旧节点，弹出时把它的每个邻居按同一张表建好或取出，再接到新邻居列表，没见过的邻居入队。对照表是同一张，只是遍历顺序不同。
起点是空，直接返回空。单节点自环：先登记再处理邻居，邻居是自己，从表里取出自己的拷贝接上，不会无限 new。不连通的图本题保证连通；若要从森林拷贝，需要对每个还没登记的节点再调一次 clone。
引用去重map 同时是「已克隆集合」和「新节点索引」。查找一次，既避免重复 new，也避免沿无向边走回已经走过的点。必须在递归邻居之前写入，自环才安全。
Go：DFS + map
func cloneGraph(node *Node) *Node {if node == nil { return nil }memo := map[*Node]*Node{}var clone func(*Node) *Nodeclone = func(n *Node) *Node {if c, ok := memo[n]; ok { return c }c := &Node{Val: n.Val, Neighbors: []*Node{}}memo[n] = cfor _, nb := range n.Neighbors {c.Neighbors = append(c.Neighbors, clone(nb))}return c}return clone(node)}
1空图直接返回。memo 的键是旧节点指针，值是对应的新节点。
2命中表就返回已有拷贝。主例从 2 走回 1、从 1 再走到已建好的 3，都走这一支。
3新建之后立刻 memo[n]=c，再递归邻居。自环在这一行之后才去 clone(自己)。
4append 的是 clone(nb) 的返回值，边上全是新指针，不会指回原图。
总结
旧→新的哈希表 + 先登记再走邻居。主例四个节点各建一次，边只连新节点。
- 没有 map，环上会死循环，或者同一节点被 new 多份。
- 先放入 map 再处理邻居，自环才安全。
- DFS 和 BFS 用同一张表，只换遍历顺序。