algorithm - 我的广度优先搜索算法有什么问题

Question

我正在学习算法类(class)，我们目前正在研究图表。我正在计算两个节点之间的最小距离。我实现了一个广度优先搜索算法来完成这个。它适用于您类(class)提供的测试用例。但是自动评分器仍然未能通过其中一项测试。它们不显示这些测试的输入或输出。有人可以看看这个并告诉我我做错了什么吗？

import java.awt.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;

public class BFS {
static int[] dist;
static Stack<Integer> stack = new Stack<Integer>();
private static int distance(ArrayList<Integer>[] adj, int s, int t) {
    dist= new int[adj.length];

    for(int i=0; i<dist.length;i++){
        dist[i]=Integer.MAX_VALUE;
    }
    dist[s]=0;
    stack.push(s);


    while(!stack.empty()){
        int u= stack.pop();
        for(int v: adj[u]){
            if(dist[v]==Integer.MAX_VALUE){
                stack.push(v);
                dist[v]=dist[u]+1;

            }

        }

    }
    if(dist[t]!=Integer.MAX_VALUE){
        return dist[t];
    }
    return -1;
}

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;
    System.out.println(distance(adj, x, y));
}
}

提前致谢。

Answer 1

您似乎实现了深度优先搜索(使用堆栈)而不是广度优先搜索(使用队列)。您的实现在以下示例中失败:

5 5
1 2
2 5
1 3
3 4
4 5
1 5

节点 1 和 5 之间的距离为 2，如路径 1-2-5 所示。但是，您的实现仅找到路径 1-3-4-5(长度为 3)，因为它按以下顺序访问边缘:

1-2 (distance 1)
1-3 (distance 1)
3-4 (distance 2)
4-5 (distance 3)
2-5 (no-op since 5 is already visited)