# Graph Java Solution

• For the example:

equations = [ ["a", "b"], ["b", "c"] ],
values = [2.0, 3.0],
queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].

build a graph like this:

connecting each the terms of each expression with a directed edge of weight 'value', and an inverted edge with weight 1/'value'.

Then you can compute the result of each query just by searching a path in the graph from var1 to var2, and multiplying the weights. E.g: ["a","c"] = a -> b -> c = 2.0 * 3.0 = 6.0
Remember to keep track of the visited nodes in the dfs , and stop as soon as you got a valid result. Return -1.0 if you hit a dead end.

Here is my code:

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
double[] results = new double[queries.length];
Map<String,List<String>> graph = buildGraph(equations,values);
for(int i=0;i<queries.length;i++) {
String[] query = queries[i];
if(query[0].equals(query[1]) && !graph.containsKey(query[0])) {
results[i]=-1.0;
}
else {
double result = computeResultDFS(graph,query);
results[i] = result;
}
}
return results;
}

public double computeResultDFS(Map<String,List<String>> graph, String[] query) {
String dividend = query[0];
String divisor = query[1];
Set<String> visited = new HashSet<>();
double result = 1.0;
result = dfs(dividend,divisor,graph,visited);
if(result<0) result = -1.;
return result;
}

public double dfs(String start, String end, Map<String,List<String>> graph, Set<String> visited) {
if(start.equals(end)) return 1.0;
if(visited.contains(start)) return -1.0;
List<String> edgesList = graph.get(start);
if(edgesList==null || edgesList.isEmpty()) return -1.0;
double result = 1.0;
for(String edge: edgesList) {
String[] tokens = edge.split(" ");
String next = tokens[0];
double val = Double.parseDouble(tokens[1]);
result = val * dfs(next,end,graph,visited);
if(result>0) return result;
}
return result;
}

public Map<String,List<String>> buildGraph(String[][] equations, double[] values) {
Map<String,List<String>> graph = new HashMap<>();
for(int i=0;i<equations.length;i++) {
String startNode = equations[i][0];
String endNode = equations[i][1];
double value = values[i];
String endEdge = endNode+" "+value;
String startEdge = startNode+" "+(1/value);
if(graph.containsKey(startNode)) {
} else {
List<String> edges = new ArrayList<>();
graph.put(startNode, edges);
}
if(graph.containsKey(endNode)) {