1、前言

2、思路

这个题目的思路就是遍历整张图，然后克隆一摸一样的图。遍历一般使用 BFS 或者 DFS。为了记录是否已经遍历了图的某个顶点，需要记录已经遍历的顶点。这里用 map 记录原始 node 与克隆 node 的关系。

3、代码

BFS：

/*
// 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 {
    public Node cloneGraph(Node node) {
        if(node == null){
            return null;
        }

        // 存储原生 node 与克隆 node 的关系
        HashMap<Node, Node> map = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        
        Node clone = new Node(node.val, new ArrayList<>());
        map.put(node, clone);
        queue.offer(node);

        while(!queue.isEmpty()){
            Node cur = queue.poll();
            for(Node n : cur.neighbors){
                if(!map.containsKey(n)){
                    Node newNode = new Node(n.val, new ArrayList<>());
                    map.put(n, newNode);
                    queue.offer(n);
                }
                map.get(cur).neighbors.add(map.get(n));
            }
        }

        return clone;
    }
}

DFS：

public Node cloneGraph(Node node) {
        HashMap<Node, Node> map = new HashMap<>();
        return dfs(node, map);
    }

    private Node dfs(Node node, HashMap<Node, Node> map){
        if(node == null){
            return null;
        }

        if(map.containsKey(node)){
            return map.get(node);
        }
        Node clone = new Node(node.val, new ArrayList<>());
        map.put(node, clone);
        for(Node n : node.neighbors){
            clone.neighbors.add(dfs(n, map));
        }

        return clone;
    }