如何使用递归对对象集合进行深度优先搜索？

Question

我用来通过其 ID 字段查找特定位置的深度优先搜索方法在遍历位置对象列表时抛出空指针异常。

我通过在 findLocation() 和 dfs() 上设置断点来调试错误，它只在 dfs() for 循环中触发 NPE。因此，例如，如果我将位置 ID 指定为“1”，则该位置将正确返回，但如果我指定的位置 ID 大于 1，则当代码进入 dfs() for 循环时，我会得到一个 NPE。

有谁知道为什么 for 循环在任何大于 1 的位置 ID 上给出 NPE？尽管位置 ID 的范围是 1 - 10。

这是通过 ID 查找位置的两种结合使用的方法：

public Location findLocation(Integer locationId) {
        Location result = null;
        for (Location l : location) {
            System.out.println("In find method...");
            result = dfs(new HashSet<Location>(), l, locationId); //line 180
            if (result != null)
                System.out.println("You are now in.." + result);
                break;
        }
        return result;
    }


private Location dfs(Set<Location> visitedAlready, Location current,
            Integer id) {
        if (current.id == id)
            return current;
        visitedAlready.add(current); 
        Location result = null;
        for (Location l : current.location) { //line 194
            result = dfs(visitedAlready, l, id);
            if (result != null)
                break;
        }
        return result;
    }

输出的确切错误如下：

Exception in thread "main" java.lang.NullPointerException
    at gmit.Location.dfs(Location.java:194)
    at gmit.Location.findLocation(Location.java:180)
    at gmit.GameParser.parse(GameParser.java:55)
    at gmit.Main.main(Main.java:28)

Answer 1

最好知道确切的错误消息是什么，等等。就此而言，要求每个 dfs() 在继续之前打印电流可能会有所帮助。

有两个潜在的罪魁祸首：首先，传递的参数 current 可能为空，这将产生 current.id == id 和 current.location 甚至可能 visitedAlready.add(current) 的错误，具体取决于关于该方法究竟试图对参数做什么。如果 Location[]（或任何集合）在 current.location 可能有空条目，就会发生这种情况。

接下来是 current.location 本身可能为 null 或者您无法使用 for 循环将 Locations 拉出的东西，因此 Location l : current.location 失败，因为 current.location 不对。的确，Location 对象有一个包含其子节点的 location 属性听起来很奇怪。

一般来说，递归深度优先搜索如下所示：

private Node findById(Set<Node> visited, Node root, Integer id) {
    int i; Node recurse;
    if (root.id == id) {
        return root;
    }
    visited.add(root);
    for (i = 0; i < root.children.length; i += 1) {
        recurse = findById(visited, root.children[i], id)
        if (result != null) {
            return result;
        }
    }
    return null;
}

如果您的代码不等同于该示例，您就会遇到麻烦。

如何使用递归对对象集合进行深度优先搜索？

How to depth first search through a collection of objects using recursion?

arrays

recursion

object

depth-first-search

java-5