# Java Memorize BFS without Recursion 中文版

• 貌似没有我这种答案的。但是私以为我这个答案是最快的。弗洛伊德算法是O(n^3),一些高票答案的话用DFS但是没有做剪枝，貌似是O(n^2)，错了还请纠正。感觉这题对于一个query,其实也就是要找图中两点之间的一条路，那么应该是BFS比较好吧。我这个应该是O(n)的，错了请纠正。希望对大家有帮助。

Floyd Alg is O(n^3). DFS without memorize can be O(n^2). I guess BFS with memorize is O(n). Correct me if I am wrong.

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

Map<String, Map<String, Double>> dp = new HashMap<>();
Map<String, Set<String>> graph = new HashMap<>();
init(dp, graph, equations, values);

double[] result = new double[queries.length];
for (int k = 0; k < result.length; k++) {
String start = queries[k][0];
String end = queries[k][1];
if (!dp.containsKey(start) || !dp.containsKey(end)) {
result[k] = -1;
continue;
}
result[k] = bfs(start, end, dp, graph, new HashSet<>());
}
return result;
}

public double bfs(String start, String end, Map<String, Map<String, Double>> dp, Map<String, Set<String>> graph, Set<String> visited) {
if (dp.get(start).containsKey(end)) return dp.get(start).get(end);
Queue<String> q = new LinkedList<>();
q.offer(start);
visited.add(start);
while (q.size() > 0) {
int size = q.size();
for (int i = 0; i < size; i++) {
String node = q.poll();
if (dp.get(node).containsKey(end)) {
dp.get(start).put(end, dp.get(start).get(node) * dp.get(node).get(end));
dp.get(end).put(start, 1 / dp.get(start).get(end));
return dp.get(start).get(end);
}
for (String child : graph.get(node)) {
if (!visited.contains(child)) {
visited.add(child);
q.offer(child);
dp.get(start).put(child, dp.get(start).get(node)*dp.get(node).get(child));
dp.get(child).put(start, 1 / dp.get(start).get(child));
}
}
}
}
return -1;
}

public void init(Map<String, Map<String, Double>> dp, Map<String, Set<String>> graph, String[][] equations, double[] values) {
for (int k = 0; k < values.length; k++) {
String start = equations[k][0], end = equations[k][1];
//for dp init
if (!dp.containsKey(start)) dp.put(start, new HashMap<>());
if (!dp.containsKey(end)) dp.put(end, new HashMap<>());
dp.get(start).put(start, 1.0);
dp.get(end).put(end, 1.0);
dp.get(start).put(end, values[k]);
dp.get(end).put(start, 1.0 / values[k]);
//for adjacency graph init
if (!graph.containsKey(start)) graph.put(start, new HashSet<>());
if (!graph.containsKey(end)) graph.put(end, new HashSet<>());
graph.get(start).add(end);
graph.get(end).add(start);
}
}
``````

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