March 17, 2019

133. Clone Graph

图的搜索类题目，用 BFS 和 DFS 都可以做。

BFS 解法: Queue + HashMap

分解开分析一共有三个步骤：

BFS 找到所有的 node。用list存所有node，hashmap存原node和新node的对应关系。
Copy nodes
Copy edges

Time = O(V+E), Space = O(V)

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        
        if (node == null) {
            return node;
        }
        
        // 1. Get all nodes
        Queue<Node> queue = new LinkedList<>();
        Set<Node> set = new HashSet<>();
        
        queue.offer(node);
        set.add(node);
        
        while (!queue.isEmpty()) {
            Node n = queue.poll();
            for (Node neighbor : n.neighbors) {
                if (!set.contains(neighbor)) {
                    set.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
        
        List<Node> nodes = new ArrayList<>(set);
        
        // 2. Copy nodes
        Map<Node, Node> map = new HashMap<>();
        for (Node n : nodes) {
            map.put(n, new Node(n.val, new ArrayList<>()));
        }
        
        // 3. Copy edges
        for (Node n : nodes) {
            Node newNode = map.get(n);
            for (Node neighbor : n.neighbors) {
                Node newNeighbor = map.get(neighbor);
                newNode.neighbors.add(newNeighbor);
            }
        }
        
        return map.get(node);
    }
}

写的精简一点：

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        Map<Node, Node> map = new HashMap<>();
        List<Node> neighbors = new ArrayList<>();
        map.put(node, new Node(node.val, neighbors));
        queue.add(node);
        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            for (Node neighbor : curNode.neighbors) {
                if (!map.containsKey(neighbor)) {
                    neighbors = new ArrayList<>();
                    map.put(neighbor, new Node(neighbor.val, neighbors)); // add nodes
                    queue.add(neighbor);
                }
                map.get(curNode).neighbors.add(map.get(neighbor));
            }
        }
        return map.get(node);
    }
}

DFS 解法

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;

    public Node() {}

    public Node(int _val,List<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        return dfs(node, map);
    }
    
    private Node dfs(Node node, Map<Node, Node> map) {
        if (map.containsKey(node)) {
            return map.get(node);
        }
        List<Node> neighbors = new ArrayList<>();
        Node newNode = new Node(node.val, neighbors);
        map.put(node, newNode);
        for (Node neiNode : node.neighbors) {
            newNode.neighbors.add(dfs(neiNode, map));
        }
        return newNode;
    }
}