克隆图

题目描述：给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

链接：https://leetcode-cn.com/problems/clone-graph/   

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：深度优先遍历

首先，如果当前节点为空，不用处理，直接返回。

否则，使用一个Map即visited来存储已经处理过的图节点和相应的克隆节点，递归处理过程如下：

• 判断当前节点是否在visited中，如果在，则说明已经处理过了，则直接从visited中取出当前节点的克隆并返回。

• 否则，根据当前节点克隆出一个新的克隆节点，新克隆的节点的邻居节点初始化为空，然后将当前节点和新的克隆节点添加到visited中；

• 然后递归处理当前节点的邻居节点。

最后，返回当前节点的克隆节点。

解法二：广度优先遍历

同样的，首先，如果当前节点为空，不用处理，直接返回。

否则，也是需要初始化一个Map即visited来存储已经处理过的图节点和相应的克隆节点，首先将当前节点和由当前节点克隆的节点添加到visited中，然后将当前节点添加到一个队列queue中，然后处理队列中的节点，知道队列不为空，处理过程如下：

• 取出队列的头结点为curNode；

• 遍历处理curNode节点的邻居节点；

• 如果当前邻居节点不在visited，则将其和相应的克隆节点添加到visited中，并将其加到队列中；

• 然后将当前邻居节点的克隆节点添加到curNode的克隆节点的邻居节点列表中。

最后，返回初始节点的克隆节点。

注：图相关的算法还是了解的不多，得多学学。

【每日寄语】 自己动手，丰衣足食！