我通过以下方式在加权有向图上实现 DFS:
public class DFSonWeightedDirectedGraph {
private static final String START = "A";
private static final String END = "C";
private int pathLength = 0;
private int stops = 0;
public static void main(String[] args) {
//this is a directed weighted graph
WeightedDirectedGraph graph = new WeightedDirectedGraph();
graph.addEdge("A", "B", 5);
graph.addEdge("A", "D", 5);
graph.addEdge("A", "E", 7);
graph.addEdge("B", "C", 4);
graph.addEdge("C", "D", 8);
graph.addEdge("C", "E", 2);
graph.addEdge("D", "C", 8);
graph.addEdge("D", "E", 6);
graph.addEdge("E", "B", 3);
LinkedList<String> visited = new LinkedList<String>();
visited.add(START);
new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
}
private void depthFirst(WeightedDirectedGraph graph, LinkedList<String> visited) {
Collection<Map.Entry<String, Integer>> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (Map.Entry<String, Integer> node : nodes) {
if (visited.contains(node.getKey())) {
continue;
}
if (node.getKey().equals(END)) {
visited.addLast(node.getKey());
pathLength += node.getValue();
stops += 1;
printPath(visited);
visited.removeLast();
pathLength -= node.getValue();
stops -= 1;
break;
}
}
// recursion
for (Map.Entry<String, Integer> node : nodes) {
if (visited.contains(node.getKey()) || node.getKey().equals(END)) {
continue;
}
visited.addLast(node.getKey());
pathLength += node.getValue();
stops += 1;
depthFirst(graph, visited);
visited.removeLast();
pathLength -= node.getValue();
stops -= 1;
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print(" ");
}
System.out.println("[path length: "+pathLength +
" stops made: "+ stops+"]");
}
}
我需要修改上面的内容,以便在搜索源节点和目标节点之间的所有路径期间允许循环。为了避免无限循环,可以根据“停止”次数或从源出发的最大允许距离设置条件来终止搜索。
例如,通过这种方式,我可以找到从 A 开始到 D 结束且恰好有 5 站的行程数量:一种解决方案可以是 ABCDCD。或者,我可以找到从 D 到 D 的距离小于 40 的不同路线的数量:一些解决方案是 DECD、DEBCD、DCDCD。
我的问题是,我不确定如何创建保持主算法搜索的逻辑,同时避免保证不会到达目标节点的无限搜索循环。
假设我想从 A 到 D。一个可能的死循环可以是 ABCEBCEBCEB....(到无穷大)。我的基于停靠次数或总行驶距离的条件可以终止此循环,但也会结束整个搜索,否则可以找到正确的路径,例如 ABCDCCDCD,当满足任一预设条件时,该搜索将正确终止。
感谢您的任何想法。
最佳答案
我认为您需要动态设置截止点/距离。例如,对于“A 到 D 正好 5 次停止”的问题,将截止值设置为 5 次停止将在达到 6 次停止时终止所有循环。如果您将截止距离设置为 40,则同样适用于问题“D 到 D 的距离小于 40”。
使用“可达性矩阵”可以提前切断一些循环,即如果存在从 i 到 j 的路径,则 a(i, j) = 1 的矩阵,否则 a(i, j) = 0 。您可以通过首先查找图形的强连通分量(使用类似 this 的算法)来构造这样的矩阵。
然后,如果目标节点无法从当前节点访问,即 a(current, target) = 0,则可以拒绝搜索循环。
关于java - DFS期间重新访问节点并控制无限循环,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1996140/