广度优先搜索错误

Question

public int bfs(int maxDepth){ //maxDepth = 3 works.. maxDepth = 4 gives me an error
        int src = 0;
        int dest = 2;
        int nodes = arr[src].length - 1;
        boolean[] visited = new boolean[nodes + 1];
        int i;
        int countDepth = 0;
        int countPaths = 0;
        int element;


        queue.add(src);

        while(!queue.isEmpty() || countDepth != maxDepth)
        {
            element = queue.remove();
            i = element;

            while(i <= nodes)
            {
                if(arr[element][i] > 0 && visited[i] == false)
                {
                    queue.add(i);
                    visited[i] = true;

                    if(arr[i][element] > 0) //if it has two directions
                        visited[i] = false;

                    if(element ==  dest || i == dest)
                        countPaths++;
                }

                i++;
            }

            countDepth++;
        }

        return countPaths;
    }

我正在尝试 'x' 关卡深度，同时计算到达目的地的路径数。

出于某种原因，我不断收到错误消息：

Exception in thread "main" java.util.NoSuchElementException
at java.util.LinkedList.removeFirst(Unknown Source)
at java.util.LinkedList.remove(Unknown Source)
at Graph.bfs(Graph.java:48)

我不明白这是怎么回事。当我深入 3 级时它似乎有效，但当我将其更改为 4 级时，它不起作用。

Answer 1

改变

while(!queue.isEmpty() || countDepth != maxDepth)

到

while(!queue.isEmpty() && countDepth != maxDepth)

每个图都有一些最大深度。看起来，您设置的 maxDepth 大于给定图形的实际可能值，并且您的循环尝试继续 bfsing 即使在处理了所有可能的节点之后（即当队列为空时）

更新我会尝试为您在评论中发布的第二个问题提供答案，即使提供的信息实际上还不够，所以，我会尝试成为 extrasens=) 我想，您将计算 length=1、length=2.. length=givenMaxDepth|maxPossibleDepth 的所有路径。我看到了 queue 数据结构，但没有看到声明 - 您是否对所有函数调用使用相同的队列？如果是，您应该在每次调用 后清除队列（调用 queue.clear() 的最佳位置是在 return 语句之前）。

此外，我看到您在每次调用中都使用了新的已访问数组，这是正确的，但如果您实际上使用了一些全局访问数组，您也应该在每次调用后 "clear" 访问 - 换句话说，用 false 填充它。

广度优先搜索错误

breadth first search error

java

runtime-error

directed-graph

breadth-first-search