depth-first-searchrecursive-backtracking

How to print path during backtracking?


I am currently working on a backtracking program and was asked to print the path for the result. Here's an example:

Imagine we are given a weighted graph, represented by adjacency list, g,

g = {
    "A": {"B": 6, "D": 1},
    "B": {"A": 6, "C": 5, "D": 2, "E": 2},
    "D": {"A": 1, "B": 2, "E": 2},
    "E": {"B": 2, "C": 5, "D": 2},
    "C": {"B": 5, "E": 5}
}

along with a start node "A" and target node "C", our goal is find the maximum value of the product of the edge weight and its path. For this example, we should find a path A -> B -> D -> E -> C, with the product of edges = 6 * 2 * 2 * 5 = 120. I have implemented a backtracking program to find the maxProduct, but I can't find a way to store the path in the class variable, List<String> path, can someone please help me to finish the implementation of storing the path into List<String> path Below is my backtracking implementation:

import java.util.*;

public class Test {
    static final String START = "A";
    static final String TARGET = "C";
    List<String> path = new ArrayList<>();
    public static void main(String[] args) {
        Map<String, Map<String, Integer>> graph = getSimplerStaticData();
        System.out.println(getMaximumPathProduct(graph, START, TARGET));
    }

    private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
        Set<String> seen = new HashSet<>();
        seen.add(start);
        return dfs(start, target, seen, graph, new LinkedList<>());
    }

    private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph, List<String> subPath) {
        if(target.equals(current)) {
            return 1;
        }

        int res = 0;
        Map<String, Integer> neighbors = graph.get(current);
        for(String neighbor: neighbors.keySet()) {
            if(!seen.contains(neighbor)) {
                seen.add(neighbor);
                int distance = neighbors.get(neighbor);
                res = Math.max(res, distance * dfs(neighbor, target, seen, graph, subPath));
                seen.remove(neighbor);
            }
        }

        return res;
    }

    private static Map<String, Map<String, Integer>> getSimplerStaticData() {
        Map<String, Map<String, Integer>> res = new HashMap<>();
        Map<String, Integer> value1 = new HashMap<>();
        value1.put("B", 6);
        value1.put("D", 1);
        res.put("A", value1);

        Map<String, Integer> value2 = new HashMap<>();
        value2.put("A", 6);
        value2.put("D", 2);
        value2.put("E", 2);
        value2.put("C", 5);
        res.put("B", value2);

        Map<String, Integer> value3 = new HashMap<>();
        value3.put("B", 5);
        value3.put("E", 5);
        res.put("C", value3);

        Map<String, Integer> value4 = new HashMap<>();
        value4.put("A", 1);
        value4.put("B", 2);
        value4.put("E", 2);
        res.put("D", value4);

        Map<String, Integer> value5 = new HashMap<>();
        value5.put("B", 2);
        value5.put("C", 5);
        value5.put("D", 2);
        res.put("E", value5);

        return res;
    }
}

Solution

  • Here is a prototype of what you want to achieve (I did not yet test it in various situations, nor try to optimize it, but it may help you start):

    import java.util.*;
    
    public class Test {
        static final String START = "A";
        static final String TARGET = "C";
        static List<String> path = new ArrayList<>();
    
        public static void main(String[] args) {
            Map<String, Map<String, Integer>> graph = getSimplerStaticData();
            System.out.println(getMaximumPathProduct(graph, START, TARGET));
            System.out.println(path);
        }
    
        private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
            Set<String> seen = new HashSet<>();
            seen.add(start);
            List<String>aPath = new ArrayList<>();
            aPath.add(start);
            return dfs(start, target, seen, graph, aPath);
        }
    
        private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph,
                                                                                            List<String> aPath) {
            if(target.equals(current))
                return 1;
    
            int res = 0;
    
            Map<String, Integer> neighbors = graph.get(current);
            for(String neighbor: neighbors.keySet()) {
                if(!seen.contains(neighbor) ) {
                    seen.add(neighbor);
                    List<String> newPath = new ArrayList<>(aPath);
                    newPath.add(neighbor);
                    int distance = neighbors.get(neighbor);
                    int newDistance = distance * dfs(neighbor, target, seen, graph, newPath);
                    if(newDistance > res){
                        res = newDistance;
                        path = newPath;
                        path.add(target);
                    }
                    seen.remove(neighbor);
                }
            }
    
            return res;
        }
    
        private static Map<String, Map<String, Integer>> getSimplerStaticData() {
            Map<String, Map<String, Integer>> res = new HashMap<>();
            Map<String, Integer> value1 = new HashMap<>();
            value1.put("B", 6);
            value1.put("D", 1);
            res.put("A", value1);
    
            Map<String, Integer> value2 = new HashMap<>();
            value2.put("A", 6);
            value2.put("D", 2);
            value2.put("E", 2);
            value2.put("C", 5);
            res.put("B", value2);
    
            Map<String, Integer> value3 = new HashMap<>();
            value3.put("B", 5);
            value3.put("E", 5);
            res.put("C", value3);
    
            Map<String, Integer> value4 = new HashMap<>();
            value4.put("A", 1);
            value4.put("B", 2);
            value4.put("E", 2);
            res.put("D", value4);
    
            Map<String, Integer> value5 = new HashMap<>();
            value5.put("B", 2);
            value5.put("C", 5);
            value5.put("D", 2);
            res.put("E", value5);
    
            return res;
        }
    }