algorithm - HackerRank上的最短到达图

我已经在hackerrank上提交了这个（https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach）问题的解决方案。它在某些测试用例中失败。我还没有弄清楚我的解决方案中有什么不正确。
问题陈述
考虑一个由n个节点组成的无向图，其中每个节点被标记为1到n，并且任意两个节点之间的边总是长度为6。我们定义节点s为BFS的起始位置。
以图的形式给出的q查询和一些起始节点，通过计算从起始节点到图中所有其他节点的最短距离来执行每个查询。然后打印一行以空格分隔的整数，列出节点s到其他每个节点的最短距离（按节点号顺序排列）；如果s与节点断开连接，则打印为到该节点的距离。
输入格式
第一行包含一个整数q，表示查询数。后面几行按以下格式描述每个查询：
第一行包含两个空格分隔的整数，分别表示图中n（节点数）和m（边数）的值。
m个后续行中的每一行i包含两个用空格分隔的整数u和v，它们描述连接节点u到节点v的边。
最后一行包含一个整数s，表示起始节点的索引。
输出格式
对于每个q查询，打印一行n-1空间分隔整数，表示从起始位置s到每个其他节点的最短距离。这些距离应按节点号（即1,2…n）顺序列出，但不应包括节点s。如果从s无法到达某个节点，则打印-1作为到该节点的距离。
例子
样本输入：

样本输出：

6 6 -1
-1 6

我的解决方案：

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static class Graph {
        //key = node. value = list of neighbors.
       Map<Integer, List<Integer>> nodes;

        public Graph(int size) {
            nodes = new HashMap<Integer, List<Integer>>();
            for(int i = 0; i<size; i++){
                nodes.put(i, new ArrayList<Integer>());
            }
        }

        public void addEdge(int first, int second) {
            if(first != second){
               if(!(nodes.get(first).contains(second))){
                    nodes.get(first).add(second);
                }
                if(!(nodes.get(second).contains(first))){
                    nodes.get(second).add(first);
                }
            }
        }

        public int[] shortestReach(int startId) { // 0 indexed
            int[] distances = new int[nodes.keySet().size()];
            Arrays.fill(distances, -1);
            distances[startId] = 0;
            visitNeighbors(startId, distances);
            return distances;
        }

        private void visitNeighbors(int startId, int[] distances){
            List<Integer> nodesToVisit = new ArrayList<Integer>();
            for(int i:nodes.get(startId)){
                if(distances[i] == -1){
                    distances[i] = distances[startId] + 6;
                    nodesToVisit.add(i);
                }
                //dont recurse right here, otherwise it will become depth-first and we will not get shortest path.
            }
            for(int i:nodesToVisit){
                visitNeighbors(i, distances);
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int queries = scanner.nextInt();

        for (int t = 0; t < queries; t++) {

            // Create a graph of size n where each edge weight is 6:
            Graph graph = new Graph(scanner.nextInt());
            int m = scanner.nextInt();

            // read and set edges
            for (int i = 0; i < m; i++) {
                int u = scanner.nextInt() - 1;
                int v = scanner.nextInt() - 1;

                // add each edge to the graph
                graph.addEdge(u, v);
            }

            // Find shortest reach from node s
            int startId = scanner.nextInt() - 1;
            int[] distances = graph.shortestReach(startId);

            for (int i = 0; i < distances.length; i++) {
                if (i != startId) {
                    System.out.print(distances[i]);
                    System.out.print(" ");
                }
            }
            System.out.println();
        }

        scanner.close();
    }
}

当我提交上述代码时，hackerrank报告某些测试用例没有通过。我不知道我做错了什么。请帮忙谢谢您。

最佳答案

这是一个很直接的问题。
您的visit方法不正确，因为它指向visitNeighbors。
使其成为一个bfs函数。目前，它是一种递归方法，使其成为stack而不是queue。

    private void visitNeighbors(int startId, int[] distances){
        List<Integer> nodesToVisit = new ArrayList<Integer>();

        nodesToVisit.add(startId);
        distances[startId] = 0;
        while (!nodesToVisit.isEmpty()) {
            int current = nodesToVisit.get(0);
            nodesToVisit.remove(0);
            for (int i : nodes.get(current)) {
                if (distances[i] == -1) {
                    distances[i] = distances[current] + 6;
                    nodesToVisit.add(i);
                }
                //dont recurse right here, otherwise it will become depth-first and we will not get shortest path.
            }
        }
    }

Here是已编辑的接受代码。

关于algorithm - HackerRank上的最短到达图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/44351096/