LeetCode刷题实战133：克隆图-轻识

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 克隆图，我们先来看题面：

https://leetcode-cn.com/problems/clone-graph/

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

题意

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

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

class Node {
    public int val;
    public List neighbors;
}

样例

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

解题

作者：爱写Bug

https://www.imooc.com/article/291263

涉及到图的遍历无非就是DFS（深度优先搜索）、BFS（广度优先搜索）

BFS就需要借助队列实现，DFS可以借助栈也可以直接用递归实现。就这道题而言直接用递归更好一些，无需开辟额外的数据结构空间记录节点。BFS、DFS写法相对固定，建议花点时间一次性理解透，一劳永逸。

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return node;
        Queue queue = new LinkedList<>();//借助队列实现BFS
        Map map = new HashMap<>();//哈希映射
        Node head = new Node(node.val, new ArrayList<>());//头节点
        map.put(node, head);//哈希映射原节点和新节点
        queue.add(node);//原节点加入到队列
        while (!queue.isEmpty()) {//队列不为空就重复循环
            Node tmp = queue.poll();//弹出队列头节点
            for (Node n : tmp.neighbors) {//遍历邻居节点
                if (!map.containsKey(n)) {//字典的键不包含该节点时
                    map.put(n, new Node(n.val, new ArrayList<>()));//新建映射关系加入字典
                    queue.add(n);//加入队列
                }
                map.get(tmp).neighbors.add(map.get(n));//加入邻居节点
            }
        }
        return head;
    }
}