Java 回溯深度优先搜索

Question

我正在尝试编写一个 DFS 来搜索以下加权图：

   0       1.       2.       3      4.     5.     6.      7.     8.   
0: 0.0,   0.68,   78.926,  6.205, 6.707, 48.45,  0.59,  0.704, 0.978, 
1: 1.47,  0.0,    116.021, 9.129, 9.869, 71.284, 0.869, 1.09,  1.44, 
2: 0.012, 0.0086, 0.0,     0.079, 0.085, 0.615,  0.007, 0.009, 0.012, 
3: 0.161, 0.109,  12.65,   0.0,   1.081, 7.807,  0.095, 0.119, 0.171, 
4: 0.149, 0.101,  11.764,  0.925, 0.0,   7.225,  0.088, 0.111, 0.146, 
5: 0.020, 0.014,  1.63,    0.128, 0.134, 0.0,    0.012, 0.015, 0.02, 
6: 1.69,  1.15,   142.86,  10.53, 11.36, 83.33   0.0,   1.254, 1.656, 
7: 1.42,  0.917,  111.11,  8.403, 9.01,  66.667, 0.797, 0.0,   1.321, 
8: 1.022, 0.69,   83.33,   5.848, 6.849, 50.0,   0.604, 0.757, 0.0,

我从有关 java 图的 corsera 教程中获得了这个 DFS 代码。我认为它会做的是找到一条从一个节点到另一个节点的图形路径——但它只是卡住了，只是一遍又一遍地向堆栈添加节点，直到它中断。

我如何更改此代码以检查从源到目标的路径，其中产品去边缘权重大于 1.0？我有点卡住了...

DFS

public Map<Integer, Integer> find(final GraphAdjMatrix adjMatrix, int source, int goal) {

    stack = new Stack<>();
    this.visited = new HashSet<>();
    this.parentMap = new HashMap<>();

    stack.push(source);
    visited.add(source);

    while (!stack.isEmpty()) {
        int curr = stack.pop();

        if (curr == goal)
            return parentMap;

        for (int n : adjMatrix.getNeighbors(curr)) {
            visited.add(n);
            parentMap.put(n, curr);
            stack.push(n);
        }
    }
    return parentMap;
}

如有任何帮助，我们将不胜感激。

Answer 1

我无法测试，因为我没有 GraphAdjMatrix class，但我认为问题在于节点已添加到 visit，但没有检查一个节点是否已经被访问过。尝试如下：

public 地图查找（最终 GraphAdjMatrix adjMatrix，int 源，int 目标）{

stack = new Stack<>();
this.visited = new HashSet<>();
this.parentMap = new HashMap<>();

stack.push(source);
visited.add(source);

while (!stack.isEmpty()) {
    int curr = stack.pop();

    if (curr == goal)
        return parentMap;

    for (int n : adjMatrix.getNeighbors(curr)) {
       if (! visited.contains(n)) {
         visited.add(n);
         parentMap.put(n, curr);
         stack.push(n);
       }
    }
}
return parentMap;

}

Java 回溯深度优先搜索

Depth First Search with backtracking in Java

java

depth-first-search