BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)

简介: BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)

BFS(广度搜索|宽度搜索)无向图遍历(JAVA手把手深入解析)


前言

       到了DFSBFS这里就是一个省一的分界线了,能搞定的省一基本没有问题,当然,也有靠纯暴力进入省一的,但是几率就会小一些。这篇文章我已经将BFS拆分的很细了呢,希望能帮助大家跨过蓝桥杯的这个分水岭。

       如果帮助到了你,请留下你的三连支持。

BFS广度搜索

       宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一,这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止

这里与DFS就有一定的区别了,他的运转方式就是横向走遍所有的节点,虽然都是从上到下,但是横向的BFS是横向挨个找,一般会使用队列来完成BFS操作。

由于DFS的代码理解难度小一些,我先准备了DFS的文章,可以先去完成DFS学习之后咱们再来完成BFS的学习,有一个从简入繁的过程:

DFS无向图遍历(JAVA手把手深入解析)_红目香薰的博客-CSDN博客

无向图

BFS与DFS的区别通过图就很明显了,而且上面我还配了一张GIF动图,相信更容易理解了,我们通过这个图再翻译成数组。

我们用BFS输出应该是:1-2-6-3-4-7-5,我们编码完毕后测试一下。

BFS全局变量定义

1、节点

为了帮助孩子们理解,我这里使用的是拼音拼写的变量【dian】

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

2、节点数

我们所有的操作都会依赖于这个长度来进行遍历,故而这里我单独写了一下:

public static int d_length=d.length;

3、根据图创建数组

这里的创建数组图的方式与DFS是相同的,咱们图一样只是遍历的方式不同而已。我就不做其它解释了。

/**
   * 图转换数组
   */
  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},
  };

4、状态记录数组

/**
* 记录每一个节点的遍历过程,走过则记录为true
*/
public static boolean[] isfStatus;

四个全局变量

这里我们共计创建了4个全局变量,依次是:

顶点、图转换数组、判断是否走过、记录每一个节点的遍历过程,走过则记录为true。

/**
   * 顶点
   */
  public static int d[] = { 1, 2, 3, 4, 5, 6, 7 };
  /**
   * 图转换数组
   */
  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},
  };
  /**
   * 顶点长度
   */
  public static int d_length=d.length;
  /**
   * 记录每一个节点的遍历过程,走过则记录为true
   */
  public static boolean[] isfStatus;

这里准备的东西其实与DFS是相同的,包括图的数组绘制理论,接下来才是真正的广搜代码内容。

BFS代码

1、队列解析

这里我们要完成BFS则需要使用队列,Java中队列会使用【Queue】来完成,这个【Queue】在【LinkedList】内,我们声明的时候直接使用:

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

来声明这个队列即可。

向队末添加元素是【offer】函数,取出第一个元素并删除是【poll】函数,我们利用队列的这两个函数就够用了。

2、广搜核心代码

广搜我们就不需要递归了,相对理解难度在于多层循环这里。我们先看一下逻辑源码:

/**
     * 队列完成的广度搜索
     */
    private static void BFS() {
      isfStatus = new boolean[d_length];
        Queue<Integer> temp = new LinkedList<Integer>();
        //遍历每个节点
        for (int i = 0; i < d_length; i++) {
          //判断当前节点是否被访问过
            if (!isfStatus[i]) {//如果没有被访问的话则将其加入队列
                System.out.print(d[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(d[k] + " ");
                            isfStatus[k] = true;
                            temp.offer(k);
                        }
                    }
                }
            }
        }
    }

从逻辑中可以看出,首先我们还是要遍历整个节点长度,然后如果是非true就代表没有走过的路线,可以进入判断,先直接输出一下这个点,因为我们图是按照从小到大排列的故而不需要考虑点的排序。

这个需要进行队列操作了,进来循环后先排队,先一处节点后再进行广度搜索的子节点添加。当然,同时走过的路线需要修改一下状态的数组下标为true。遍历范围还是从第一个点遍历到最后一个点。

3、遍历节点

理论与DFS相同

全局控制:变量【i】,我们通过变量【i】来控制我们遍历的行数,这样就能逐一击破了。

初始点:坐标点需要从最左侧的0开始遍历,只要找到不是0的数就代表有链接点了。

下一个链接:坐标得从第N个开始遍历了,因为之前的已经遍历过了。这里的N是变量【j】。

// 返回与i相连的第一个顶点
    private static int firstValue(int i) {
        for (int j = 0; j < d_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 < d_length; k++) {
            if (arr[i][k] > 0) {
                return k;
            }
        }
        return -1;
    }

4、最终输出

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

可以看到最终结果与深度搜索的目标结果是相同的,代表我们遍历是没有问题的。

完整代码对照

package com.item.action;
import java.util.LinkedList;
import java.util.Queue;
 
public class Demo5 {
  /**
   * 顶点
   */
  public static int d[] = { 1, 2, 3, 4, 5, 6, 7 };
  /**
   * 图转换数组
   */
  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},
  };
  /**
   * 顶点长度
   */
  public static int d_length=d.length;
  /**
   * 记录每一个节点的遍历过程,走过则记录为true
   */
  public static boolean[] isfStatus;
  
    /**
          * 队列完成的广度搜索
     */
    private static void BFS() {
      isfStatus = new boolean[d_length];
        Queue<Integer> temp = new LinkedList<Integer>();
        //遍历每个节点
        for (int i = 0; i < d_length; i++) {
          //判断当前节点是否被访问过
            if (!isfStatus[i]) {//如果没有被访问的话则将其加入队列
                System.out.print(d[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(d[k] + " ");
                            isfStatus[k] = true;
                            temp.offer(k);
                        }
                    }
                }
            }
        }
    }
    // 返回与i相连的第一个顶点
    private static int firstValue(int i) {
        for (int j = 0; j < d_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 < d_length; k++) {
            if (arr[i][k] > 0) {
                return k;
            }
        }
        return -1;
    }
 
    // 测试
    public static void main(String args[]) {
        BFS();
    }
}

完整代码留在这里是帮助大家对照的啊,别直接复制用,这样意义就不那么高了。

总结

       我们咋做蓝桥杯题的时候很多的时候都是有套路的,我们很多时候通过我们背过的一些套路去套题目也会直接出结果的,例如全排列的方法,还有很多的公式,欧几里得,欧拉等等,都是很方便的,我们其实不是算法的创造者,我们只是知识的搬运工,争取将更多的知识搬运到咱们的大脑中啊。

连续的两篇文章我们对DFS于BFS都做了一定的理解,有了这个基础我们才能更好的应对各省的省赛题目,当然,最难的题目应该还是DP类型题,所以后面我们还是需要更好的去读题,理解题,用量来积累,千万别看到难题就跑,我们可以先不搭理它,先去解决一些简单的题目,通过在简单题目中累积的解题思路来一点点摸索出解题规律,解题技巧。

3月份前没有DP分享了,3月份的时候请将各省的省赛题的前6~7题做一遍,简单的先搞定了再说难的8~10题,整个3月份就会针对8~10题进行加强训练了,那个时候简单题的意义就不大了,为了省一,加油。

相关文章
|
13天前
|
Java
Java中ReentrantLock释放锁代码解析
Java中ReentrantLock释放锁代码解析
25 8
|
Java
java实现遍历树形菜单方法——OpenSessionView实现
java实现遍历树形菜单方法——OpenSessionView实现
12 0
|
1月前
|
Java
java实现遍历树形菜单方法——TreeAction实现
java实现遍历树形菜单方法——TreeAction实现
9 0
|
1月前
|
Java
java实现遍历树形菜单方法——HibernateUtil实现
java实现遍历树形菜单方法——HibernateUtil实现
10 0
|
1月前
|
Java
java实现遍历树形菜单方法——service层
java实现遍历树形菜单方法——service层
11 0
|
Java
java实现遍历树形菜单方法——index.jsp实现
java实现遍历树形菜单方法——index.jsp实现
6 0
|
7天前
|
Java API 数据库
深入解析:使用JPA进行Java对象关系映射的实践与应用
【4月更文挑战第17天】Java Persistence API (JPA) 是Java EE中的ORM规范,简化数据库操作,让开发者以面向对象方式处理数据,提高效率和代码可读性。它定义了Java对象与数据库表的映射,通过@Entity等注解标记实体类,如User类映射到users表。JPA提供持久化上下文和EntityManager,管理对象生命周期,支持Criteria API和JPQL进行数据库查询。同时,JPA包含事务管理功能,保证数据一致性。使用JPA能降低开发复杂性,但需根据项目需求灵活应用,结合框架如Spring Data JPA,进一步提升开发便捷性。
|
11天前
|
Java
Java 15 神秘登场:隐藏类解析未知领域
Java 15 神秘登场:隐藏类解析未知领域
15 0
|
11天前
|
安全 Java 编译器
接口之美,内部之妙:深入解析Java的接口与内部类
接口之美,内部之妙:深入解析Java的接口与内部类
34 0
接口之美,内部之妙:深入解析Java的接口与内部类
|
29天前
|
JSON JavaScript 数据格式
【深入探究C++ JSON库】解析JSON元素的层级管理与遍历手段
【深入探究C++ JSON库】解析JSON元素的层级管理与遍历手段
87 2

推荐镜像

更多