求一个在DFS里print path的代码

题目是这样：provide了一个adjacency list的weighted graph，然后需要通过backtracking return maximumProduct和他的path。例子如下：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}
}
Expected: method getMaximumPathProduct() 应该return 120，variable List<String> path = ["A", "B", "D", "E", "C"]
楼主已经通过backtracking得到了maximumProduct，但是卡在了如何记录path. 代码贴在下面了，请大神们对其做更改，需要能run的code~ 感谢！

PS: 想再问一下时间复杂度以及有没有pruning的可能

1. import java.util.ArrayList;
   
2. import java.util.HashMap;
   
3. import java.util.HashSet;
   
4. import java.util.LinkedList;
   
5. import java.util.List;
   
6. import java.util.Map;
   
7. import java.util.Set;
   
8. 
   
9. public class Test {
   
10.     static final String START = "A";
    
11.     static final String TARGET = "C";
    
12.     List<String> path = new ArrayList<>();
    
13.     public static void main(String[] args) {
    
14.         Map<String, Map<String, Integer>> graph = getSimplerStaticData();
    
15.         System.out.println(getMaximumPathProduct(graph, START, TARGET));
    
16.     }
    
17. 
    
18.     private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
    
19.         Set<String> seen = new HashSet<>();
    
20.         seen.add(start);
    
21.         return dfs(start, target, seen, graph, new LinkedList<>());
    
22.     }
    
23. 
    
24.     private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph, List<String> subPath) {
    
25.         if(target.equals(current)) {
    
26.             return 1;
    
27.         }
    
28. 
    
29.         int res = 0;
    
30.         Map<String, Integer> neighbors = graph.get(current);
    
31.         for(String neighbor: neighbors.keySet()) {
    
32.             if(!seen.contains(neighbor)) {
    
33.                 seen.add(neighbor);
    
34.                 int distance = neighbors.get(neighbor);
    
35.                 res = Math.max(res, distance * dfs(neighbor, target, seen, graph, subPath));
    
36.                 seen.remove(neighbor);
    
37.             }
    
38.         }
    
39. 
    
40.         return res;
    
41.     }
    
42. 
    
43.     private static Map<String, Map<String, Integer>> getSimplerStaticData() {
    
44.         Map<String, Map<String, Integer>> res = new HashMap<>();
    
45.         Map<String, Integer> value1 = new HashMap<>();
    
46.         value1.put("B", 6);
    
47.         value1.put("D", 1);
    
48.         res.put("A", value1);
    
49. 
    
50.         Map<String, Integer> value2 = new HashMap<>();
    
51.         value2.put("A", 6);
    
52.         value2.put("D", 2);
    
53.         value2.put("E", 2);
    
54.         value2.put("C", 5);
    
55.         res.put("B", value2);
    
56. 
    
57.         Map<String, Integer> value3 = new HashMap<>();
    
58.         value3.put("B", 5);
    
59.         value3.put("E", 5);
    
60.         res.put("C", value3);
    
61. 
    
62.         Map<String, Integer> value4 = new HashMap<>();
    
63.         value4.put("A", 1);
    
64.         value4.put("B", 2);
    
65.         value4.put("E", 2);
    
66.         res.put("D", value4);
    
67. 
    
68.         Map<String, Integer> value5 = new HashMap<>();
    
69.         value5.put("B", 2);
    
70.         value5.put("C", 5);
    
71.         value5.put("D", 2);
    
72.         res.put("E", value5);
    
73. 
    
74.         return res;
    
75.     }
    
76. }
    

复制代码

1.     static int maxRes = 0;
   
2.     private static int getMaximumPathProduct(Map<String, Map<String, Integer>> graph, String start, String target) {
   
3.         Set<String> seen = new HashSet<>();
   
4.         seen.add(start);
   
5.         return dfs(start, target, seen, graph, new LinkedList<>(), 1);
   
6.     }
   
7.     private static int dfs(String current, String target, Set<String> seen, Map<String, Map<String, Integer>> graph, LinkedList<String> subPath, int curProd) {
   
8.         subPath.add(current);
   
9.         if(target.equals(current)) {
   
10.             if (maxRes < curProd) {
    
11.                 path = (List<String>) subPath.clone();
    
12.                 maxRes = curProd;
    
13.             }
    
14.             subPath.removeLast();
    
15.             return 1;
    
16.         }
    
17.         ......................
    
18.                 res = Math.max(res, distance * dfs(neighbor, target, seen, graph, subPath, curProd * distance));
    
19.         ...................
    
20.         subPath.removeLast();
    
21.         return res;
    
22.     }

复制代码

這不是Ford–Fulkerson max flow問題？