题解 | #牛群之间的体重比#

题目考察的知识点是：

哈希，BFS算法。

题目解答方法的文字分析：

本题可以根据给定的牛群体重比关系，找出问题中给定的牛群体重之间的比值。可以将牛群体重比关系建立成一个图，然后利用深度优先搜索或广度优先搜索的方法来找到问题中牛群体重的比值。如果在搜索过程中找不到某个牛的体重比关系，则返回-1.0作为答案。

本题解析所用的编程语言：

java语言。

完整且正确的编程代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param weightRatios string字符串二维数组
     * @param ratioValues double浮点型一维数组
     * @param questions string字符串二维数组
     * @return double浮点型一维数组
     */
    public double[] calcWeightRatios (String[][] weightRatios, double[] ratioValues,
                                      String[][] questions) {
        Map<String, Map<String, Double>> graph = buildGraph(weightRatios, ratioValues);
        double[] answers = new double[questions.length];
        for (int i = 0; i < questions.length; i++) {
            String startNode = questions[i][0];
            String endNode = questions[i][1];
            if (!graph.containsKey(startNode) || !graph.containsKey(endNode)) {
                answers[i] = -1.0;
                continue;
            }
            Set<String> visited = new HashSet<>();
            double result = dfs(graph, startNode, endNode, 1.0, visited);
            answers[i] = result;
        }
        return answers;
    }

    private Map<String, Map<String, Double>> buildGraph(String[][] weightRatios,
            double[] ratioValues) {
        Map<String, Map<String, Double>> graph = new HashMap<>();
        for (int i = 0; i < weightRatios.length; i++) {
            String sourceNode = weightRatios[i][0];
            String targetNode = weightRatios[i][1];
            double weightRatio = ratioValues[i];
            graph.putIfAbsent(sourceNode, new HashMap<>());
            graph.get(sourceNode).put(targetNode, weightRatio);
            graph.putIfAbsent(targetNode, new HashMap<>());
            graph.get(targetNode).put(sourceNode, 1.0 / weightRatio);
        }
        return graph;
    }

    private double dfs(Map<String, Map<String, Double>> graph, String currentNode,
                       String endNode, double value, Set<String> visited) {
        if (currentNode.equals(endNode)) {
            return value;
        }
        visited.add(currentNode);
        if (!graph.containsKey(currentNode)) {
            return -1.0;
        }
        for (Map.Entry<String, Double> neighbor : graph.get(currentNode).entrySet()) {
            String nextNode = neighbor.getKey();
            double weightRatio = neighbor.getValue();
            if (!visited.contains(nextNode)) {
                double result = dfs(graph, nextNode, endNode, value * weightRatio, visited);
                if (result != -1.0) {
                    return result;
                }
            }
        }
        return -1.0;
    }
}