java - 深度优先/广度优先算法打印所有节点；我如何让它只打印路径中的节点？

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 的迷宫的邻接矩阵，如果:

1. x != y
2. x 与 y 相邻
3. 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

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

• 你的 Start 和 end 是错误的:它应该减 1(因为 指数从 0 开始)
• 你的邻接矩阵是错误的(它的大小是 10X9 - 它应该是一个平方矩阵)(编辑修复它)
• 您的解决方案应该只打印路径中的元素。一种方法是返回 List<> (而不是 void - 填充当前路径中的所有节点。如果到达目的地，则创建列表，否则 - 返回 null 。仅当递归调用返回不是 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]

---

作为旁注，虽然这个解决方案是完整的(如果存在，总能找到解决方案)，但它不是最佳的 - 它可能会返回比最短的。

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