迷宫寻路(图可达性)Java代码本地通过但提交报错，求帮忙排查错误

问题根因 #

你的DFS遍历逻辑存在缺陷，遍历当前节点的邻接节点时，只要第一个未访问的邻接点递归完成就直接终止了整个遍历流程，不会检查剩余的邻接节点。如果目标节点不在第一个邻接点的子树中，就会出现误判不可达的问题。

错误逻辑分析 #

你现有代码中reach函数的循环部分：

while(itr.hasNext()){
    x = (int)itr.next();
    if(!visited[x]){
        return reach(adj,x,y);
    }
}

这里只要碰到第一个未访问的邻接点，不管递归返回的结果是1（找到）还是0（没找到），都会直接return跳出整个函数，剩余的邻接点永远不会被遍历，自然会漏掉可达路径。同时你在循环里直接覆盖了参数x的取值，也存在变量复用的逻辑隐患。

修正方案 #

调整递归返回逻辑：只有当递归调用返回1（找到目标节点）时才向上返回1，否则继续遍历下一个邻接点，所有邻接点都遍历完成仍未找到再返回0，同时用单独变量存储邻接节点避免覆盖参数。

修正后的完整代码 #

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Iterator;

public class Reachability {

    private static boolean[] visited;

    private static int reach(ArrayList<Integer>[] adj, int x, int y) {
        if(x == y){
            return 1;
        }
        
        visited[x] = true;
        Iterator itr = adj[x].iterator();
        while(itr.hasNext()){
            int next = (int)itr.next();
            if(!visited[next]){
                int res = reach(adj,next,y);
                // 只有找到目标才返回，没找到继续遍历其他邻接点
                if(res == 1) {
                    return 1;
                }
            }
        }
        return 0;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < m; i++) {
            int x, y;
            x = scanner.nextInt();
            y = scanner.nextInt();
            adj[x - 1].add(y - 1);
            adj[y - 1].add(x - 1);
        }
        int x = scanner.nextInt() - 1;
        int y = scanner.nextInt() - 1;
        visited = new boolean[n];
        System.out.println(reach(adj, x, y));
    }
}

内容的提问来源于stack exchange，提问作者Thulina Wickramasinghe