Java DFS in directed-weight graph, no Node class


  • 0
    L

    I referenced https://discuss.leetcode.com/topic/60910/ac-java-codes-using-graph-idea/2
    but did a bit modification: I remove the Node class.

    
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            Map<String,Map<String,Double>> graph = new HashMap<>();
    
            // construct graph
            for (int i = 0; i < equations.length; i++) {
                String op1 = equations[i][0];
                String op2 = equations[i][1];
                double val = values[i];
    
                // create edge (two directions, different weight)
                Map<String,Double> op1Map = graph.get(op1);
                if(op1Map == null){
                    op1Map = new HashMap<>();
                    graph.put(op1,op1Map);
                }
                op1Map.put(op2,val);
    
                Map<String,Double> op2Map = graph.get(op2);
                if(op2Map == null){
                    op2Map = new HashMap<>();
                    graph.put(op2,op2Map);
                }
                op2Map.put(op1,1/val);
            }
    
            // dfs find path
            double[] result = new double[queries.length];
            for (int i = 0; i < queries.length; i++) {
                //注意:先处理边界情况,因为DFS默认双方都在graph中
                String op1 = queries[i][0];
                String op2 = queries[i][1];
                if(!graph.containsKey(op1) || !graph.containsKey(op2)) result[i]=-1;
                else if(op1.equals(op2)) result[i]=1;
                else
                    result[i] = dfs(graph,op1,op2,new HashSet<>());
            }
            return result;
        }
    
        // find path from start to end, get evaluate result
        private double dfs(Map<String,Map<String,Double>> graph,String start,String end,Set<String> visited){
            if(visited.contains(start)) return -1.0;
            // traverse all neighbours
            visited.add(start); //在这加了visited就不要再在loop加了
            Map<String,Double> neighbourMap = graph.get(start);
            for(Map.Entry<String,Double> entry: neighbourMap.entrySet()){
                String neighbour = entry.getKey();
                double edgeWeight = entry.getValue();
                if(neighbour.equals(end)){ //found
                    return edgeWeight;
                }
                double temp = dfs(graph,neighbour,end,visited);
                if(temp > 0){   //found
                    return temp*edgeWeight;
                }
            }
            return -1.0; //not found
        }
    
    

Log in to reply
 

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