如何在回溯过程中打印路径

Question

我目前正在开发一个回溯程序，并被要求打印结果的路径。这里有一个例子：

想象一下，我们得到了一个加权图，由邻接表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}
}

连同起始节点"；A"；以及目标节点"；C"；，我们的目标是找到边权重及其路径的乘积的最大值。对于这个例子，我们应该找到一个路径a->B->D->E->C、 边的乘积=6*2*2*5=120。我已经实现了一个回溯程序来查找maxProduct，但我找不到将路径存储在类变量List<String> path中的方法，有人能帮我完成将路径存储到List<String> path中的实现吗？下面是我的回溯实现：

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;
}
}

Answer 1

这里有一个你想要实现的原型(我还没有在各种情况下测试它，也没有尝试优化它，但它可能会帮助你开始(：

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;
}
}