java graph bfs solution


  • 0
    P

    First, build a graph with the given equations in two directions, then for each query, for example, "a/b" search the path from "a" to "b".

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
            HashMap<String, Double> map = new HashMap<>(); //edge -> value   for example: "a/b" -> 2.0
            Set<String> vetex = new HashSet<>(); //vertices
            HashMap<String, Set<String>> edge = new HashMap<>(); //edges
            double[] res = new double[query.length];
            for(int i = 0; i < values.length; i++) {
                String div = equations[i][0], dvd = equations[i][1];
                vetex.add(div); 
                vetex.add(dvd);
                map.put(div + "/" + dvd, values[i]);
                map.put(dvd + "/" + div, 1 / values[i]);
                if(!edge.containsKey(div)) {
                    edge.put(div, new HashSet<String>());
                }
                if(!edge.containsKey(dvd)) {
                    edge.put(dvd, new HashSet<String>());
                }
                Set<String> set1 = edge.get(div);
                set1.add(dvd);
                Set<String> set2 = edge.get(dvd);
                set2.add(div);
            }
            for(int i = 0; i < query.length; i++) {
                String div = query[i][0], dvd = query[i][1];
                double r;
                if(!vetex.contains(div) || !vetex.contains(dvd)) {
                    r = -1.0;
                } else if(div.equals(dvd)){
                    r = 1.0;
                } else {
                    r = BFS(div, dvd, map, edge);
                }
                res[i] = r;
            }
            return res;
        }
        
        public double BFS(String div, String dvd, HashMap<String, Double> map, HashMap<String, Set<String>> edge) {
            if(map.containsKey(div + "/" + dvd)) {
                return map.get(div + "/" + dvd);
            }
            Queue<String> queue = new LinkedList<String>();
            HashSet<String> visited = new HashSet<String>();
            queue.add(div);
            while(!queue.isEmpty()) {
                String src = queue.poll();
                visited.add(src);
                if(!edge.containsKey(src))  continue;
                Set<String> set = edge.get(src);
                for(String v : set) {
                	if(visited.contains(v))
                		continue;
                    queue.add(v);
                    if(!map.containsKey(div + "/" + v)) {
                        double val1 = map.get(div + "/" + src);
                        double val2 = map.get(src + "/" + v);
                        map.put(div + "/" + v, val1 * val2);
                    }
                    if(!map.containsKey(v + "/" + div)) {
                        map.put(v + "/" + div, 1 / map.get(div + "/" + v));
                    }
                    if(v.equals(dvd)) {
                        return map.get(div + "/" + v);
                    }
                }
            }
            return -1.0;
        }
    }
    

  • 0
    H

    I love your solution. However, the Set for vertices is exactly the same as the keys in edges so it is unnecessary. I also trimmed some other lines to get my answer. Thank you so much!

    public class Solution {
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            double[] res = new double[queries.length];
            //Construct a graph with directed edges, vertices and weights
            Map<String, Set<String>> edges = new HashMap<>();
            // Set<String> vertices = new HashSet<>();
            Map<String, Double> weights = new HashMap<>();
            
            for (int i=0; i<equations.length; i++)
                addToGraph(edges, weights, equations[i][0], equations[i][1], values[i]);
           
            
            for (int i=0; i<queries.length; i++) {
                String top = queries[i][0];
                String bottom = queries[i][1];
                if (!edges.containsKey(top) || !edges.containsKey(bottom)) res[i] = -1.0;
                else if (top.equals(bottom)) res[i] = 1.0;
                else res[i] = bfs(edges, weights, top, bottom);
            }
            return res;
        }
        
        private void addToGraph(Map<String, Set<String>> edges, Map<String, Double> weights, String top, String bottom, double v){
    
            if (!edges.containsKey(top)) edges.put(top, new HashSet<String>());
            if (!edges.containsKey(bottom)) edges.put(bottom, new HashSet<String>());;
            edges.get(top).add(bottom);
            edges.get(bottom).add(top);
            weights.put(top+"/"+bottom, v);
            weights.put(bottom+"/"+top, 1/v);
        }
        
        private double bfs(Map<String, Set<String>> edges, Map<String, Double> weights, String top, String bottom) {
          
            if (weights.containsKey(top+"/"+bottom)) return weights.get(top+"/"+bottom);
            Queue<String> q = new LinkedList<>();
            Set<String> visited = new HashSet<>();
            q.add(top);
            while(!q.isEmpty()) {
                String src = q.poll();
                visited.add(src);
                Set<String> adjacentVertices = edges.get(src);
               
                for (String v: adjacentVertices) {
                    if (visited.contains(v)) continue;
                    q.add(v);
                    if(!weights.containsKey(top + "/" + v)) {
                        double v1 = weights.get(top+"/"+src);
                        double v2 = weights.get(src+"/"+v);
                        addToGraph(edges, weights, top, v, v1*v2);
                    }
                    if (v.equals(bottom)) return weights.get(top+"/"+v);
                }
            }
            return -1.0;
        }
        
        
    }
    

  • 0
    P

    @hayleyhu You're right, it looks much better now!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.