克隆图

记住「先查表、没有才新建」这一招，下面每一步都在用它。

原图在这里：6 个节点、若干条边。我们要在右侧逐个建出它们的副本。

访问节点 1：查哈希表 map，里面还没有它 → 新建副本 1'，并写入 map[1]=1'。

节点 1 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

访问节点 2：查哈希表 map，里面还没有它 → 新建副本 2'，并写入 map[2]=2'。

节点 2 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

连边：原图里 1—2 相邻，于是在克隆图里把副本 1' 和 2' 也连起来（map 里取出两端的克隆节点）。

访问节点 4：查哈希表 map，里面还没有它 → 新建副本 4'，并写入 map[4]=4'。

节点 4 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

连边：原图里 1—4 相邻，于是在克隆图里把副本 1' 和 4' 也连起来（map 里取出两端的克隆节点）。

访问节点 3：查哈希表 map，里面还没有它 → 新建副本 3'，并写入 map[3]=3'。

节点 3 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

连边：原图里 1—3 相邻，于是在克隆图里把副本 1' 和 3' 也连起来（map 里取出两端的克隆节点）。

访问节点 5：查哈希表 map，里面还没有它 → 新建副本 5'，并写入 map[5]=5'。

节点 5 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

连边：原图里 1—5 相邻，于是在克隆图里把副本 1' 和 5' 也连起来（map 里取出两端的克隆节点）。

连边：原图里 2—3 相邻，于是在克隆图里把副本 2' 和 3' 也连起来（map 里取出两端的克隆节点）。

连边：原图里 2—5 相邻，于是在克隆图里把副本 2' 和 5' 也连起来（map 里取出两端的克隆节点）。

连边：原图里 4—3 相邻，于是在克隆图里把副本 4' 和 3' 也连起来（map 里取出两端的克隆节点）。

访问节点 6：查哈希表 map，里面还没有它 → 新建副本 6'，并写入 map[6]=6'。

节点 6 克隆完成，加入「已克隆」面板。它的邻居稍后入队，依次同样处理。

连边：原图里 4—6 相邻，于是在克隆图里把副本 4' 和 6' 也连起来（map 里取出两端的克隆节点）。

连边：原图里 3—6 相邻，于是在克隆图里把副本 3' 和 6' 也连起来（map 里取出两端的克隆节点）。

全部节点都克隆了、全部边都连上了——右侧面板里 6 个副本就是这张图的深拷贝，返回起点的副本即可。

边界先想清。

两个高频追问。