133. Clone Graph

我们也可以使用 BFS 来遍历图，使用队列 queue 进行辅助，还是需要一个 HashMap 来建立原图结点和克隆结点之间的映射。先克隆当前结点，然后建立映射，并加入 queue 中，进行 while 循环。在循环中，取出队首结点，遍历其所有 neighbor 结点，若不在 HashMap 中，我们根据 neigbor 结点值克隆一个新 neighbor 结点，建立映射，并且排入 queue 中。然后将 neighbor 结点在 HashMap 中的映射结点加入到克隆结点的 neighbors 数组中即可

Map.containsKey() :是否含有key

Map.get(key) :  获取key对应的value

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

399. Evaluate Division

用有向图的方法做，先存入图中，再用DFS遍历。

Map.keySet() : 获取map对应的所有的key值。

class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        Map<String, Map<String, Double>> g = new HashMap<>();
        buildGraph(g, equations, values);
        
        double[] res = new double[queries.size()];
        Arrays.fill(res, -1.0);
        int index = 0;
        for(List<String> q : queries){
            String a = q.get(0);
            String b = q.get(1);
            
            if(!g.containsKey(a) || !g.containsKey(b)){
                index++;
                continue;
            }else{
                dfs(g, a, b, res, index, new HashSet<>(), 1.0);
                index++;
            }
        }
        return res;
    }
    
    private void dfs(Map<String, Map<String, Double>> g, String a, String b, double[] res,
                     int index, Set<String> visited, double tmp){
        visited.add(a);
        
        if(g.get(a) == null || g.get(a).size() == 0){
            return;
        }
        if(g.get(a).containsKey(b)){
            res[index] = g.get(a).get(b) * tmp;
            return;
        }
        
        for(String next : g.get(a).keySet()){
            if(visited.contains(next)) continue;
            dfs(g, next, b, res, index, visited, g.get(a).get(next)*tmp);
        }
    }
    
    private void buildGraph(Map<String, Map<String, Double>> g, List<List<String>> equations, double[] values){
        int index = 0;
        for(List<String> e : equations){
            String a = e.get(0);
            String b = e.get(1);
            g.putIfAbsent(a, new HashMap<>());
            g.putIfAbsent(b, new HashMap<>());
            g.get(a).put(b, values[index]);
            g.get(b).put(a, 1.0 / values[index]);
            index++;
            g.get(a).put(a, 1.0);
            g.get(b).put(b, 1.0);
        }
    }
}