133. Clone Graph (BFS, DFS)

BFS

time: O(m+n), m is nodes number, n is edges number

space: O(m), for queue and visited set

/*
// 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;
    }
}
   1     2     3     4 
[[2,4],[1,3],[2,4],[1,3]]

*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        
        List<Node> nodes = findAllNodes(node);
        Map<Node, Node> mapping = copyNodes(nodes);
        copyEdges(nodes, mapping);
        
        return mapping.get(node);
    }
    
    private List<Node> findAllNodes(Node node) {
        Queue<Node> queue = new ArrayDeque<>();
        Set<Node> visited = new HashSet<>();
        
        queue.offer(node);
        visited.add(node);
        
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            for (Node neighbor : cur.neighbors) {
                
                if (!visited.contains(neighbor)) {
                    queue.offer(neighbor);
                    visited.add(neighbor);
                }
            }
        }
        return new LinkedList<>(visited);
    }
    
    private Map<Node, Node> copyNodes(List<Node> nodes) {
        Map<Node, Node> mapping = new HashMap<>();
        for (Node node : nodes) {
            mapping.put(node, new Node(node.val));
        }
        return mapping;
    }
    private void copyEdges(List<Node> nodes, Map<Node, Node> mapping) {
        for (Node node : nodes) {
            Node newNode = mapping.get(node);
            for (Node neighbor : node.neighbors) {
                newNode.neighbors.add(mapping.get(neighbor));
            }
        }
    }

}

DFS

T: O(n)
S: O(n)

```java
/*
// 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;
    }
}

dfs
邊遍利 邊copy

T: O(n)
S: O(n)
*/

class Solution {
    public Node cloneGraph(Node node) {
        Map<Integer, Node> map = new HashMap<>();
        Set<Integer> visited = new HashSet<>();
        return dfs(node, map, visited);
    }
    private Node dfs(Node node, Map<Integer, Node> map, Set<Integer> visited) {
        if (node == null) {
            return null;
        }
        if (visited.contains(node.val)) { // 2
            return map.get(node.val);
        }
        visited.add(node.val);
        Node newNode = new Node(node.val);
        map.put(node.val, newNode); // map(1, newNode(1)), map(2, newNode(2)), map(2, newNode(3)), map(2, newNode(4))

        for (Node next : node.neighbors) { // 2, 4, 1,3, (2,4), (1,3)
            newNode.neighbors.add(dfs(next, map, visited)); // dfs(1) -> attach to newNode(2), attach to newNode(3), attach to newNode(4), (4)...
        }
        return newNode;
    }
}
```