需要帮助使用广度优先搜索 (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

由于在执行 bfs 时每个节点都应与其深度相关联，因此您可以创建一个 class 来存储节点和深度（如果要打印路径，还包括父节点）：

package Whosebug;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

public class BFSTest {
    public static class BFSNode {
        public int node, depth;
        public BFSNode parent;

        public BFSNode(int node) {
            this.node = node;
            this.depth = 0;
            this.parent = null;
        }

        public BFSNode(int node, BFSNode parent) {
            this.node = node;
            this.depth = parent.depth+1;
            this.parent = parent;
        }
    }

    ArrayDeque<BFSNode> queue;
    int[][] arr;

    public BFSTest() {
        queue = new ArrayDeque<BFSNode>();
        arr = new int[5][5];
        arr[0][1] = arr[0][3] = arr[0][4] = 1;
        arr[1][2] = 1;
        arr[2][3] = arr[2][4] = 1;
        arr[3][2] = arr[3][4] = 1;
        arr[4][1] = 1;
    }

    public int bfs(int src, int dest, int maxDepth){
        int i;
        int countPaths = 0;
        BFSNode element;

        queue.add(new BFSNode(src));

        while(!queue.isEmpty())
        {   
            element = queue.poll();
            if (element.depth > maxDepth)
                break;
            i = 0;

            while(i < 5) 
            {   
                if(arr[element.node][i] > 0)
                {
                    if(i == dest && element.depth +1 <= maxDepth) {
                        BFSNode tmp = element;
                        List<Integer> path = new ArrayList<Integer>();
                        path.add(dest);
                        while (tmp != null) {
                            path.add(tmp.node);
                            tmp = tmp.parent;
                        }
                        for (int j = path.size() - 1; j >= 0; j--) {
                            System.out.print(path.get(j) + " ");
                        }
                        System.out.println();
                        countPaths++;
                    }

                    queue.add(new BFSNode(i, element));

                }       
                i++;
            }
        }

        queue.clear();
        return countPaths;
    }

    public static void main(String[] args) {
        BFSTest test = new BFSTest();
        System.out.println(test.bfs(2, 2, 3));
        System.out.println(test.bfs(0, 2, 3));
    }

}

你得到

//src = 2, dest=2
2 3 2   //path 1
2 4 1 2 //path 2
2       //total
//src=0. dest=2
0 1 2   //path 1
0 3 2   //path 2
0 4 1 2 //path 3
3       //total

Answer 2

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

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

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 循环将保证所有级别都将被处理（或只是其中的一些，如果你扩展停止循环的条件）。

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

Need help getting to nth level of an adjacency matrix (graph) using a breadth-first search (Java)

java

algorithm

directed-graph

breadth-first-search

adjacency-matrix