algorithm - HackerRank 上的最短距离图

Question

我已经在 HackerRank 上提交了这个 ( https://www.hackerrank.com/challenges/ctci-bfs-shortest-reach) 问题的解决方案。对于某些测试用例，它会失败。我无法弄清楚我的解决方案中有什么不正确的地方。

问题陈述

考虑一个由 n 个节点组成的无向图，其中每个节点都被标记为从 1 到 n 并且任何两个节点之间的边总是长度 6。我们将节点 s 定义为 BFS 的起始位置。

给定 q 个图形形式的查询和一些起始节点 s ，通过计算距起始节点 s 的最短距离来执行每个查询 em> 到图中的所有其他节点。然后打印一行以空格分隔的整数，列出节点 s 到每个其他节点的最短距离(按节点编号顺序排列)；如果 s 与节点断开连接，则打印为到该节点的距离。

输入格式

第一行包含一个整数，q，表示查询的数量。后续行按以下格式描述每个查询:

第一行包含两个以空格分隔的整数，分别描述图中n(节点数)和m(边数)的值。 m 行中的每一行 i 包含两个用空格分隔的整数，u 和 v，描述一条边将节点 u 连接到节点 v。 最后一行包含一个整数s，表示起始节点的索引。

输出格式

对于每个 q 查询，打印一行 n-1 空格分隔的整数，表示从起始位置到每个其他节点的最短距离 < em>s。这些距离应按节点编号顺序列出(即 1,2...n)，但不应包括节点 s。如果某个节点无法从 s 到达，则打印 -1 作为到该节点的距离。

示例

示例输入:

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

示例输出:

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 报告说某些测试用例没有通过。我不确定我做错了什么。请帮忙。谢谢。

Answer 1

这是一个非常直接的 bfs 问题。

考虑到它指向 visitNeighbors，您的 visit 方法不正确。

让它成为一个 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是编辑后的接受代码。