java - 需要帮助使用广度优先搜索 (Java) 进入邻接矩阵(图形)的第 n 级

Question

public int bfs(int maxDepth){
        int src = 2;
        int dest = 2;
        int i;
        int depth = 0;
        int countPaths = 0;
        int element;

        queue.add(src);

        while(!queue.isEmpty() && depth <= maxDepth)
        {   
            element = queue.remove();
            i = 0;

            while(i < 5) 
            {   
                if(arr[element][i] > 0)
                {
                    queue.add(i);

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

        queue.clear();
        return countPaths;
    }

您好!!给定源和目的地，我需要找到一条路径。就遍历图形而言，我的 BFS 算法运行良好。我的问题是让它在我想要的时候停止。我去掉了我增加深度的地方，所以我看起来不像一个彻头彻尾的白痴。我希望有人能帮帮忙。本质上，我想知道如何跟踪当前深度。谢谢!

例子:

找出从 C 到 C 的路径数，最多停靠点数为 3。答案是两条路:

C -> D -> C(2 站)

C -> E -> B -> C(3 站)

示例 2:查找从 A 到 C 的路径数，最多停靠点数为 3。答案是三个路径。

A -> B -> C(2 站)

A -> D -> C(2 站)

A -> E -> B -> C -> (3 站)

Answer 1

Q: Essentially I want to know how I can keep track of the current depth.

一种解决方案是创建一个带有附加字段 depth 的包装器类，正如@svs 在他的回答中所解释的那样。但是，有一个巧妙的技巧可以避免创建包装器类，而且它非常简单:

queue.add(src);
while(!queue.isEmpty())
{
     int size = queue.size();
     for(int i=0; i<size; i++)
     {
     .. //do processing for the current depth
     }
}

在 for 循环中，您可以对该级别的节点执行任何您打算执行的操作，包括将新元素放入队列中(深度等于 current_depth + 1 的节点)。在for 循环中只迭代queue.size() 次将保证您只处理当前级别的节点，而while 循环将保证所有级别都将被处理(或者如果您扩展停止循环的条件，则只处理其中的一些级别)。