# java graph bfs solution

• 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];
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);
Set<String> set2 = edge.get(dvd);
}
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);
}
HashSet<String> visited = new HashSet<String>();
while(!queue.isEmpty()) {
String src = queue.poll();
if(!edge.containsKey(src))  continue;
Set<String> set = edge.get(src);
for(String v : set) {
if(visited.contains(v))
continue;
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;
}
}
``````

• 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++)

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>());;
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);
Set<String> visited = new HashSet<>();
while(!q.isEmpty()) {
String src = q.poll();

if (visited.contains(v)) continue;
if(!weights.containsKey(top + "/" + v)) {
double v1 = weights.get(top+"/"+src);
double v2 = weights.get(src+"/"+v);
}
if (v.equals(bottom)) return weights.get(top+"/"+v);
}
}
return -1.0;
}

}
``````

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

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