# Use graph to solve the problem with explanation

• ``````public class Solution {

/**
* Use graph to solve the question
*
* Mode:
* The node of the graph is the string, the edge is the value
* For Example: a / b = 2.0, then we have two nodes: 'a', 'b'. the two edges between 'a' and 'b'
*  Edge: a->b is 2.0
*  Edge: b->a is 1.0/2.0 (0.5)
*
* When we do the query, we just need to do the graph search. I am using BFS here. We travel the tree and multiple the edge value alone the way. then we can find the anser
* For Exampe:  a/b = 2.0   b/c = 3.0:
*      Case 1: Query a/c
*      a/c = (a/b)*(b/c), That is why we can get the answer multiple the edge value
*      Case 2: Query c/a
*      c/a = (c/b)*(b/a). That is the reason we create two edges, now the algorithm is same as case 1. just multiple the edge value
*      Case 3: can't find the divident in the graph, return -1
*      Case 4: can't find the divisor in the graph, return -1
*
* */

private class Edge{
public String s=null;
public double v=0.0;

public Edge(String s, double v){
this.s = s;
this.v = v;
}
}

private HashMap<String, List<Edge>> g = new HashMap();

public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
process(equations, values);

double[] res = new double[queries.length];

for(int i=0; i<queries.length; i++){
res[i] = find(queries[i][0], queries[i][1]);
}
return res;
}
/**
* creat the graph data
* */
private void process(String[][] equations, double[] values){
for(int i=0; i<equations.length; i++){

//creat two edges
Edge foward = new Edge(equations[i][1], values[i]);
Edge backward = new Edge(equations[i][0], 1.0/values[i]);

if(!g.containsKey(equations[i][0])){
g.put(equations[i][0], new ArrayList<Edge>());
}
if(!g.containsKey(equations[i][1])){
g.put(equations[i][1], new ArrayList<Edge>());
}

}
}

/**
* Do the BFS to find the answer
* */
private double find(String from, String to){

double res = -1.0;
if(!g.containsKey(from)){
return res;
}
HashSet<String> visited = new HashSet();

while(!q.isEmpty()){
String nextS = q.poll();
double nextV = qv.poll();
if(nextS.equals(to)){
//found
res = nextV;
return res;
}

List<Edge> neighbor = g.get(nextS);
for(Edge n: neighbor){
if(!visited.contains(n.s)){