Depth-first/breadth-first算法打印所有节点；我如何让它只打印路径中的节点？

Question

我有一个如下形式的邻接矩阵adj：

0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0 
1 0 0 0 1 0 1 0 0 
0 0 0 1 0 1 0 0 0 
0 0 1 0 1 0 0 0 1 
0 0 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 0

这是具有规则 adj(x,y) = 1 的迷宫的邻接矩阵，如果：

x != y
x 与 y 相邻
x 或 y 都不是迷宫中的墙

迷宫如下（旁边是元素编号）：

S X E | 1 2 3
O O O | 4 5 6
O X O | 7 8 9
//S = starting position
//E = ending position
//X = wall

我有一个 DFS 算法，它会显示从 S 到 E 遍历的节点，但它会显示不必要的节点。

public static void main(String [] args){
    int[][] adj = //the adjacency matrix
    boolean[] visited = new boolean[adj.length];
    int n = adj.length;    
    int m = 1; //starting position
    int o = 3; //ending position
    DFS(adjMatrix, visited, n, m, o);
}

public static void DFS(int[][] adj, boolean[] visited, int n, int i, int o){
    System.out.print(" " + (i+1));
    visited[i]= true;
    if (i+1 != o) {
        for (int j = 0; j<n;j++){
            if(!(visited[j]) && adj[i][j]==1){
               DFS(adj, visited, n, j, o);
            }
        }
    }
}

public static void BFS(int[][] adj, boolean[] visited, int n, int i, int o){
    queue Q = new queue;
    visited[i]= true;
    Q.enqueue(i);
    while (!Q.isEmpty()) {
        //...
    }
}

这会打印 1 4 5 6 3 9 7。我正在绞尽脑汁修改它，以便它只会打印 1 4 5 6 3.

我做错了什么？

Answer 1

尝试使用此代码：

public static boolean DFS(int[][] adj, boolean[] visited, int n, int i, int o){        
    visited[i]= true;
    boolean good = false;
    if (i+1 != o) {
        for (int j = 0; j<n;j++){
            if(!(visited[j]) && adj[i][j]==1){
               good |= DFS(adj, visited, n, j, o);
            }
        }
    } else {
        good = true;
    }
    if (good) System.out.print(" " + (i+1));
    return good;
}

这将反向打印路径（从头到尾）- 但它只会打印属于良好路径一部分的节点。如果需要按照从头到尾的顺序打印路径，可以将其存储在一个数组中，然后反向打印：

public static void DFS(int[][] adj, boolean[] visited, 
       ArrayList<int> path, int n, int i, int o){        
    visited[i]= true;
    if (i+1 != o) {
        for (int j = 0; j<n;j++){
            if(!(visited[j]) && adj[i][j]==1){
               path.add(j);
               DFS(adj, visited, n, j, o);
               path.remove(path.size()-1);
            }
        }
    } else {
        // show path
        for (int i : path) {
            System.out.print(" " + i);
        }
    }        
}

Answer 2

当您最终到达目的地时，方法堆栈将具有路径。

  ArrayList<Integer> list = new ArrayList<>(); // this will have your path.
  public static boolean DFS(int[][] adj, boolean[] visited, int n, int i, int o){
    if(i==o){
       list.add(o);
      //System.out.println(i);
      return true;
    }
    visited[i]= true;
    for (int j = 0; j<n;j++){
       if(!(visited[j]) && adj[i][j]==1){
          if(DFS(adj, visited, n, j, o)){
              list.add(0,j);
              //System.out.println(j);
              return true;
           }
         }
     }
   return false;
  }

Answer 3

除了 DFS 算法所需的修复之外，代码还存在一些主要问题：

你的 Start 和 end 是错误的：应该减 1（因为索引基于 0)
~~你的邻接矩阵是错误的（它的大小是 10X9 - 它应该是一个平方矩阵）~~（编辑修复它）
您的解决方案应该只打印路径中的元素。一种方法是 return a List<> （而不是 void - 填充当前路径中的所有节点。如果到达目的地，请创建列表，否则 - return null。仅当递归调用 return 不是 null 时附加元素。附加代码

另请注意，它以正确的顺序（而不是颠倒的顺序）打印节点

public static void main(String [] args){
    int[][] adj = {
            {0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 1, 0, 0, 0}, 
            {1, 0, 0, 0, 1, 0, 1, 0, 0}, 
            {0, 0, 0, 1, 0, 1, 0, 0, 0}, 
            {0, 0, 1, 0, 1, 0, 0, 0, 1}, 
            {0, 0, 0, 1, 0, 0, 0, 0, 0}, 
            {0, 0, 0, 0, 0, 0, 0, 0, 0}, 
            { 0, 0, 0, 0, 0, 1, 0, 0, 0} 
    };
    boolean[] visited = new boolean[adj.length];
    int n = adj.length;    
    int m = 1-1; //starting position
    int o = 3-1; //ending position
    System.out.println(DFS(adj, visited, n, m, o));
}

public static List<Integer> DFS(int[][] adj, boolean[] visited, int n, int i, int o){
    visited[i]= true;
    if (i == o) return new LinkedList<Integer>(Arrays.asList(i+1));
    for (int j = 0; j<n;j++){
        if(!(visited[j]) && adj[i][j]==1){
            List<Integer> res = DFS(adj, visited, n, j, o);
            if (res != null) { 
                res.add(0, i+1);
                return res;
            }
        }
    }
    return null; //no path
}

结果（如预期）：

[1, 4, 5, 6, 3]

附带说明一下，尽管此解决方案完整（如果存在，总会找到解决方案），但它不是最佳 - 它可能 return 比最短的解决方案更长。

如果您想找到从源到目标的最短路径，请考虑切换到 BFS

Depth-first/breadth-first算法打印所有节点；我如何让它只打印路径中的节点？

Depth-first/breadth-first algorithm printing all nodes; how do I get it to only print nodes in the path?

java

algorithm

nodes

depth-first-search

adjacency-matrix