克隆图

Leetcode题目描述

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

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

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

详细题目描述看一下链接

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clone-graph

深度优先解法

问题的核心是一致的:避免重复地遍历同一个节点，或者是重复遍历一条路径。可以采用哈希表的方式进行判断，鉴于每一个Node节点哦都是不一致的，作为Hash的Key就不会出现的重复的现象。而Hash的Vuale可以选择被克隆的节点加入。

• 注意Neighbor是使用List方式进行存储。所以添加邻居节点时，使用List中的add方法直接添加。
• 注意其中的构造方法，关键在于第三个的构造方法。

深度优先demo

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    // 创建一个哈希表，key是源节点，Value是克隆节点
    private HashMap<Node,Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        // 返回节点为空时的状态
        if (node == null) return node;

        // 如果这个节点已经被访问过，那么返回这个克隆节点
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // 创建一个新节点，那么只是克隆其中的一个节点，不克隆其中的邻居节点
        Node cloneNode = new Node(node.val, new ArrayList());
        visited.put(node, cloneNode);

        //从节点邻居入，开始添加到克隆节点的邻居节点中
        for (Node neighbor: node.neighbors){
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }

        return cloneNode;
    }
}