克隆图的两种解法 LC133 clone graph

克隆图
克隆图的话需要注意图是可能有环的。所以要避免绕进去。

BFS做法：
先完全clone它自己， 对它的孩子，都只是注册一下（只在hashMap里注册一下，不深度copy)
把他所有的孩子放到队列里面。把它标记为visited。然后走完Queue
注意注册的时候就要丢到队列里面。

DFS做法：
先copy value， 注册自己。然后把孩子搞定，如果孩子注册过了，拿过来用就行。
如果孩子没注册过，掉转枪头搞孩子，最后自己才算 搞定。
如果搞孩子的过程中发现循环了，又循环到自己头上， 因为自己已经注册过了，所以直接拿来用就行。

class Solution {
    public Node cloneGraph(Node node) {
        Map<Node, Node> nodeMap = new HashMap<>();
        return cloneHelper(node, nodeMap);
    }
    private Node cloneHelper(Node node, Map<Node, Node> nodeMap) {
        if (nodeMap.containsKey(node)) return nodeMap.get(node);
        Node clonedNode = new Node(node.val, new ArrayList<>());
        nodeMap.put(node, clonedNode);
        for (Node nei : node.neighbors) {
            clonedNode.neighbors.add(cloneHelper(nei, nodeMap));
        }
        return clonedNode;
    }
}

BFS做法

    public Node cloneGraph(Node node) {
        Map<Node, Node> nodeMap = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        nodeMap.put(node, new Node(node.val, new ArrayList<>()));
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            Node clonedCur = nodeMap.get(cur);
            for (Node nei : cur.neighbors) {
                if (!nodeMap.containsKey(nei)) {
                    nodeMap.put(nei, new Node(nei.val, new ArrayList<>()));
                    queue.offer(nei);
                }
                clonedCur.neighbors.add(nodeMap.get(nei));
            }
        }
        return nodeMap.get(node);
    }