Java广度搜索---BFS方法解析

- 日理万妓 2024-03-26 11:01 19阅读 0赞

参考文章，原文链接：[(10条消息) BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)\_红目香薰的博客-CSDN博客\_bfs遍历][10_ BFS_JAVA_-CSDN_bfs]

部分图片，代码 来自参考文章

先理解BFS（深度搜索有助于理解BFS方法）3

[(10条消息) java--DFS深度搜索方法\_CLODVEP的博客-CSDN博客\_java dfs][10_ java--DFS_CLODVEP_-CSDN_java dfs]

## **BFS（**[**广度搜索**][Link 1]**）方法理论与理解** ##

广度搜索就是

**广度优先搜索. 广度优先搜索算法 （英語： Breadth-First Search ，縮寫為BFS），又譯作 寬度優先搜索 ，或 橫向優先搜索 ，是一種 圖形搜索演算法 。. 簡單的說，BFS是從 根節點 開始，沿着树的宽度遍历树的 节点 。. 如果所有节点均被访问，则算法中止。**

![c55ea806651cede7ed6cf95b66ffd491.gif][]

也可以说说是逐级遍历

根据距离顶点的距离可以分为多级节点

（内部也可以说x的n级节点）

方便理解我们以1为一级，看实际顺序就是，逐级从左向右输出

也就是先输出所有下一级节点，再进入下一级，

![8e718e6e3962240de8d8357078364d70.jpeg][]

![9be0e247d1164cd79d397bc086c99845.png][]

## **BFS方法的实现** ##

### **数据准备，数据输入** ###

我们需要**四个全局变量，全局变量！！！**

这里的数据都是以上面的为例子

#### 1，节点数，所有节点的记录 ####

dian即节点（方便理解，随意命名可以），类型为需要的类型，

需要将每一个节点录入该数组，顺序可以随意（下面的二维图转换数组的顺序需要对照这个循序，所以晴考虑一下）

public static String dian[] = { "1", "2", "3", "4", "5", "6", "7" };

#### **2、全节点数，数组长度、节点数量的记录** ####

即所有节点的数量，

下面会按照这个长度来遍历，就是上面数组的长度，

直接定义也刑， .length也行

publicstaticint dian_length=dian.length;

#### 3、二维数组，链接关系的记录 ####

这个数组可以存储，每一个节点 所链接的节点都有哪些（包括上、下级）；

创建的规则：

，如果有n给节点，就创建n\*n的二维数组，

、第n行必须对应 节点数组 的 第n个节点

标注规则：

链接到对应的节点就标注 1

没有链接对应节点就标注 0

如果对应的节点是自身标注 0

这里用示例包含7个节点，所以7\*7的二维数组

··········-----------

节点1 链接节点2、6，所以再第2、6位上就标注1

以此类推

public static int[][] arr= {
                {0,1,0,0,0,1,0},
                {1,0,1,1,0,0,0},
                {0,1,0,0,0,0,0},
                {0,1,0,0,1,0,0},
                {0,0,0,1,0,0,0},
                {1,0,0,0,0,0,1},
                {0,0,0,0,0,1,0},
        };

#### 5、队列方法-在函数内定义 ####

向队末添加元素是 offer 函数，

**取出**第一个元素**并删除**是poll

Queue<Integer> temp = new LinkedList<Integer>();

#### 4、布尔数组，是否遍历的记录 ####

从对方法的理解中，我们知道，再没有下级节点的时候，我们需要返回

并且继续遍历没有遍历的节点

所有我们需要记录节点是否遍历锅，

定义一个布尔类型的数组，记录所有节点的状态

将所有节点初始状态为False（因为初始的布尔数组都是False）

再遍历的过程中改为true

我们就知道状态为true的节点就是遍历过的节点

public static boolean[] isfStatus;

### **数据处理，深度搜索** ###

理解遇到困难可以翻到该部分最下面，有示意图

1.  #### **广搜核心代码** ####

核心原理就是

//将所有子节点加入队列，队列根据顺序遍历，所以确保是按照等级遍历所有节点

private static void BFS() {
            isfStatus = new boolean[dian_length];
            Queue<Integer> temp = new LinkedList<Integer>();
            //遍历每个节点
            for (int i = 0; i < dian_length; i++) {
                //判断当前节点是否被访问过
                if (!isfStatus[i]) {
                    System.out.print(dian[i] + " ");
                    isfStatus[i] = true;
                    //如果没有被访问的话则将其加入队列
                    temp.offer(i);
                    while (!temp.isEmpty()) {
                        //将队列的第一个节点移除
                        int j = temp.poll();
                        //搜索、遍历他的下级节点
                        for (int k = firstValue(j); k >= 0; k = nextValue(j, k)) {
                            if (!isfStatus[k]) {
                                System.out.print(dian[k] + " ");
                                isfStatus[k] = true;
                                //将所有子节点加入队列，
                                //队列根据顺序遍历，所以确保是按照等级
                                temp.offer(k);
                            }
                        }
                    }
                }
            }
        }

#### 2、遍历方法，子节点的确定与遍历 ####

原理就是

通过判定二维数组里的1确定有哪个节点有链接

// 返回与i相连的第一个顶点
        private static int firstValue(int i) {
            for (int j = 0; j < dian_length; j++) {
                if (arr[i][j] > 0) {
                    return j;
                }
            }
            return -1;
        }
        // 返回与i相连的下一个顶点
        private static int nextValue(int i, int j) {
            for (int k = (j + 1); k < dian_length; k++) {
                if (arr[i][k] > 0) {
                    return k;
                }
            }
            return -1;
        }

#### 3、输出结果 ####

public static void main(String args[]) {
            BFS();
        }

### 示意图- ###

![39f684037d11b22242c5385048d3c0e9.jpeg][]

![b5ab847abee0206889d2141bfc3117c0.jpeg][]

![998fe4f722db46222e3165108a0c2c9e.jpeg][]

[10_ BFS_JAVA_-CSDN_bfs]: https://blog.csdn.net/feng8403000/article/details/128992846?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522167679525016800213062932%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=167679525016800213062932&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_ecpm_v1~rank_v31_ecpm-1-128992846-null-null.blog_rank_default&utm_term=bfs&spm=1018.2226.3001.4450
[10_ java--DFS_CLODVEP_-CSDN_java dfs]: https://blog.csdn.net/m0_73932182/article/details/128997037
[Link 1]: https://so.csdn.net/so/search?q=%E6%B7%B1%E5%BA%A6%E6%90%9C%E7%B4%A2&spm=1001.2101.3001.7020
[c55ea806651cede7ed6cf95b66ffd491.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/2bd0d0964077452e9af8de30175f14b6.png
[8e718e6e3962240de8d8357078364d70.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/441c2e94127c490dbe20d583398810ca.png
[9be0e247d1164cd79d397bc086c99845.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/e666dad435c14fb1b280cd0587715b31.png
[39f684037d11b22242c5385048d3c0e9.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/09424f77bffc4017bd5ef3c11280bbd5.png
[b5ab847abee0206889d2141bfc3117c0.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/368d8abe503647e89aaeadf7be66e470.png
[998fe4f722db46222e3165108a0c2c9e.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fc07913eb68d490a90688a50e809e8de.png