# Simple Java Graph and DFS with explanation

• Simple Directed Graph and DFS
based on equations and value, we need to construct directed graph along with weight.
E.g a/b=2 then we a-->b with weight 2 and b--->a with weight 1/2. the same for b/c=3 and the rest. when we need to query a/c we need do a/c=a/b * b/c. use regular DFS ways to do it.

Note: a/a and x/x are special cases.

welcome for any suggestions.

``````
// this is directional graph, use dfs to calculate them.
public static double[] calcEquation(String[][] equations, double[] values, String[][] query) {
//construct directed graph
HashMap<String, List<DirectedEdge>> graph = new HashMap<String, List<DirectedEdge>>();
List<String> onStack = new ArrayList<String>();
int index = 0;
for (String[] pair : equations) {
List<DirectedEdge> list1 = graph.getOrDefault(pair[0], new ArrayList<DirectedEdge>());
graph.put(pair[0], list1);
List<DirectedEdge> list2 = graph.getOrDefault(pair[1], new ArrayList<DirectedEdge>());
list2.add(new DirectedEdge(pair[1], pair[0], 1 / values[index]));
graph.put(pair[1], list2);
index++;
}
double[] result = new double[query.length];
index = 0;
for (String[] qry : query) {
double temp = -1;
// calculate the result
onStack.clear();
if (canReach(qry[0], qry[1], graph, onStack)) {
temp = 1;
for (int i = 0; i < onStack.size() - 1; i++) {
List<DirectedEdge> list = graph.get(onStack.get(i));
for (DirectedEdge de : list) {
if (de.w.equals(onStack.get(i + 1))) {
temp = temp * de.weight;
break;
}
}
}

}
result[index++] = temp;

}
return result;

}

public static boolean canReach(String var1, String var2, HashMap<String, List<DirectedEdge>> graph,
List<String> onStack) {
boolean found = false;
if (graph.containsKey(var1)) {
if (var1.equals(var2)) {
found = true;
} else {
for (DirectedEdge de : graph.get(var1)) {
if (de.v.equals(var2)) {
found = true;
break;
} else if (de.w.equals(var2)) {
found = true;
break;
}
if (!onStack.contains(de.w)) {
if (canReach(de.w, var2, graph, onStack)) {
return true;
}
onStack.remove(onStack.size() - 1);
}
}
}
}
return found;

}

public static class DirectedEdge {
private final String v; // edge source
private final String w; // edge target
private final double weight; // edge weight

public DirectedEdge(String v, String w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}

public double weight() {
return weight;
}

public String from() {
return v;
}

public String to() {
return w;
}

@Override
public boolean equals(Object obj) {
// TODO Auto-generated method stub
DirectedEdge de2 = (DirectedEdge) obj;
return this.v.equals(de2.v);
}

}

``````

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