Graph (Java) - ShuweiLeung/Thinking GitHub Wiki

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
        HashMap<String, ArrayList<String>> pairs = new HashMap<String, ArrayList<String>>(); //pairs和valuesPair的value list相同位置上的元素一一对应
        HashMap<String, ArrayList<Double>> valuesPair = new HashMap<String, ArrayList<Double>>();
        for (int i = 0; i < equations.length; i++) {  //存储a/b关系和b/a关系，对应的值分别为x和1/x
            String[] equation = equations[i];
            if (!pairs.containsKey(equation[0])) {
                pairs.put(equation[0], new ArrayList<String>());
                valuesPair.put(equation[0], new ArrayList<Double>());
            }
            if (!pairs.containsKey(equation[1])) {
                pairs.put(equation[1], new ArrayList<String>());
                valuesPair.put(equation[1], new ArrayList<Double>());
            }
            pairs.get(equation[0]).add(equation[1]);
            pairs.get(equation[1]).add(equation[0]);
            valuesPair.get(equation[0]).add(values[i]);
            valuesPair.get(equation[1]).add(1/values[i]);
        }
        
        double[] result = new double[queries.length];
        for (int i = 0; i < queries.length; i++) {  //dfs搜索从起点到终点的一条路径
            String[] query = queries[i];
            result[i] = dfs(query[0], query[1], pairs, valuesPair, new HashSet<String>(), 1.0); //set集合用来表示遍历过的元素，防止重复遍历陷入死循环
            if (result[i] == 0.0) result[i] = -1.0;
        }
        return result;
    }
    
    private double dfs(String start, String end, HashMap<String, ArrayList<String>> pairs, HashMap<String, ArrayList<Double>> values, HashSet<String> set, double value) {
        if (set.contains(start)) return 0.0; //之前遍历过的元素
        if (!pairs.containsKey(start)) return 0.0; //起点或终点不存在
        if (start.equals(end)) return value; //起点就是终点，直接返回传入的value值
        set.add(start); //将起点加入set中
        
        ArrayList<String> strList = pairs.get(start); //与起点相邻的结点
        ArrayList<Double> valueList = values.get(start);
        double tmp = 0.0; //起点到终点的代价
        for (int i = 0; i < strList.size(); i++) {
            tmp = dfs(strList.get(i), end, pairs, values, set, value*valueList.get(i));
            if (tmp != 0.0) {
                break;
            }
        }
        set.remove(start); //从set集合中删除起点
        return tmp;
    }