Java实现广度优先遍历的示例详解

目录
  • 什么是广度优先
  • 一个简单的例子
  • 程序实现
  • 总结

什么是广度优先

广度就是扩展开,广度优先的意思就是尽量扩展开。所以在算法实现的时候,就是一个循环遍历枚举每一个邻接点。其基本思路就是按层扩展,扩得越广越好。

伪代码如下:

for(int i = 0; i < children.size(); i++){
    children.get(i); // 调用每一个子节点
}

一个简单的例子

我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫。

1 1 0 1 1 1 1 1 1

1 0 0 0 0 0 0 1 1

1 0 1 1 1 1 0 1 1

1 0 0 0 0 0 0 0 1

1 1 1 1 1 1 1 0 1

以上面这个0为入口,下面这个0为出口,那么广度优先的算法遍历顺序就为:dp[0][2]为入口,扩展出dp[1][2],继续扩展出dp[1][1]和dp[1][3],我把这个过程列在下面了:

第一步:

dp[0][2] -> dp[1][2]

第二步:

dp[1][2] -> dp[1][1] & dp[1][3]

第三步:

dp[1][1] -> dp[2][1]

dp[1][3] -> dp[1][4]

第四步:

dp[2][1] -> dp[3][1]

dp[1][4] -> dp[1][5]

第五步:

dp[3][1] -> dp[3][2]

dp[1][5] -> dp[1][6]

第六步:

dp[3][2] -> dp[3][3]

dp[1][6] -> dp[2][6]

第七步:

dp[3][3] -> dp[3][4]

dp[2][6] -> dp[3][6]

第八步:

dp[3][4] -> dp[3][5]

dp[3][6] -> dp[3][7]

第九步:

dp[3][5] -> dp[3][6]

dp[3][7] -> dp[4][7] ->到达终点

算法结束

好了,如果你已经懂了,就赶快去写代码吧。你可以使用一个二维数组来构建这个迷宫,然后思考怎么实现状态流转。

程序实现

要实现一个简单例子中的程序,我们需要编写输入函数,处理迷宫为01字符数组,然后编写bfs函数作为主体函数,然后我们怎么让代码表现出行走状态呢?假定当前坐标为 x,y,要行走,本质上就是判断 (x-1,y) (x+1,y) (x,y+1) (x,y-1) 是否可以走,所以我们需要编写一个判定函数,用来验证边界条件,这也是bfs里面的核心函数之一。以Java代码为例

package com.chaojilaji.book;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Bfs {

    public static String[][] getInput(String a) {
        String[] b = a.split("\n");
        int n = 0, m = 0;
        m = b.length;
        for (int i = 0; i < b.length; i++) {
            String[] c = b[i].split("  ");
            n = c.length;
            break;
        }
        String[][] x = new String[m][n];
        for (int i = 0; i < b.length; i++) {
            String[] c = b[i].split("  ");
            for (int j = 0; j < c.length; j++) {
                x[i][j] = c[j];
            }
        }
        return x;
    }

    public static Boolean canAdd(String[][] a, Integer x, Integer y, Set<Integer> cache) {
        int m = a[0].length;
        int n = a.length;
        if (x < 0 || x >= m) {
            return false;
        }
        if (y < 0 || y >= n) {
            return false;
        }
        if (a[y][x].equals("0") && !cache.contains(x * 100000 + y)) {
            cache.add(x * 100000 + y);
            return true;
        }
        return false;
    }

    public static Integer bfs(String[][] a) {
        // 规定入口在第一行,出口在最后一行
        int m = a[0].length;
        int n = a.length;
        int rux = -1, ruy = 0;
        int chux = -1, chuy = n - 1;
        for (int i = 0; i < m; i++) {
            if (a[0][i].equals("0")) {
                // TODO: 2022/1/11 找到入口
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Integer ans = 0;
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        List<Integer> nexts = new ArrayList<>();
        nexts.add(rux * 100000 + ruy);
        while (true) {
            if (nexts.size() == 0) {
                ans = -1;
                break;
            }
            int flag = 0;
            List<Integer> tmpNexts = new ArrayList<>();
            for (Integer next : nexts) {
                int x = next / 100000;
                int y = next % 100000;
                if (x == chux && y == chuy) {
                    flag = 1;
                    break;
                }
                // TODO: 2022/1/11 根据现在的坐标,上下左右走
                if (canAdd(a, x - 1, y, cache)) tmpNexts.add((x - 1) * 100000 + y);
                if (canAdd(a, x + 1, y, cache)) tmpNexts.add((x + 1) * 100000 + y);
                if (canAdd(a, x, y - 1, cache)) tmpNexts.add(x * 100000 + (y - 1));
                if (canAdd(a, x, y + 1, cache)) tmpNexts.add(x * 100000 + (y + 1));
            }
            nexts.clear();
            nexts.addAll(tmpNexts);
            if (flag == 1) {
                break;
            }else {
                ans++;
            }
        }
        return ans;
    }

    public static void demo() {
        String a = "1  1  0  1  1  1  1  1  1\n" +
                "1  0  0  0  0  0  0  1  1\n" +
                "1  0  1  1  1  1  0  1  1\n" +
                "1  0  0  0  0  0  0  0  1\n" +
                "1  1  1  1  1  1  1  0  1";
        String[][] b = getInput(a);

        Integer ans = bfs(b);
        System.out.println(ans == -1 ? "不可达" : "可达,最短距离为" + ans+"步");
    }

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

这是数组的写法,这也是这个简单场景的写法。不过在我们的实际生活中,更多的会使用队列来实现广度优先搜索。队列模式下广度优先搜索的伪代码如下:

queue a;
while(!a.empty()){
	a.take();
    处理
    将扩展出来的结果入队
}

那么上面这个迷宫,我们就可以使用标准广度优先模板来实现,具体代码如下:

public static Integer bfsQueue(String[][] a) {
        Queue<Integer> queue = new LinkedList<>();
        int m = a[0].length;
        int n = a.length;
        int rux = -1, ruy = 0;
        int chux = -1, chuy = n - 1;
        for (int i = 0; i < m; i++) {
            if (a[0][i].equals("0")) {
                // TODO: 2022/1/11 找到入口
                rux = i;
            }
            if (a[n - 1][i].equals("0")) {
                chux = i;
            }
        }
        Integer ans = 0;
        Set<Integer> cache = new HashSet<>();
        cache.add(rux * 100000 + ruy);
        queue.add(rux * 100000 + ruy);
        Map<Integer, Integer> buzi = new HashMap<>();
        buzi.put(rux * 100000 + ruy, 0);
        int flag = 0;
        while (!queue.isEmpty()) {
            Integer val = queue.poll();
            int x = val / 100000;
            int y = val % 100000;
            if (x == chux && y == chuy) {
                flag = 1;
                ans = buzi.get(x * 100000 + y);
                break;
            }
            // TODO: 2022/1/11 根据现在的坐标,上下左右走
            if (canAdd(a, x - 1, y, cache)) {
                buzi.put((x - 1) * 100000 + y, buzi.get(x * 100000 + y)+1);
                queue.add((x - 1) * 100000 + y);
            }
            if (canAdd(a, x + 1, y, cache)) {
                buzi.put((x + 1) * 100000 + y, buzi.get(x * 100000 + y)+1);
                queue.add((x + 1) * 100000 + y);
            }
            if (canAdd(a, x, y - 1, cache)) {
                buzi.put(x * 100000 + (y - 1), buzi.get(x * 100000 + y)+1);
                queue.add(x * 100000 + (y - 1));
            }
            if (canAdd(a, x, y + 1, cache)) {
                buzi.put(x * 100000 + y + 1, buzi.get(x * 100000 + y)+1);
                queue.add(x * 100000 + (y + 1));
            }
        }
        if (flag == 1){
            return ans;
        }
        return -1;
    }

这段代码就可以替换掉上一段代码中的bfs函数。将上面的代码合并到一起,执行的结果为:

可见,两段代码的结果是一致的。

总结

简单总结一下,广度优先算法实现的时候主要需要解决两个问题。即,如何扩展(行走),临界判断。

到此这篇关于Java实现广度优先遍历的示例详解的文章就介绍到这了,更多相关Java广度优先遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 基于Java实现的图的广度优先遍历算法

    本文以实例形式讲述了基于Java的图的广度优先遍历算法实现方法,具体方法如下: 用邻接矩阵存储图方法: 1.确定图的顶点个数和边的个数 2.输入顶点信息存储在一维数组vertex中 3.初始化邻接矩阵: 4.依次输入每条边存储在邻接矩阵arc中 输入边依附的两个顶点的序号i,j: 将邻接矩阵的第i行第j列的元素值置为1: 将邻接矩阵的第j行第i列的元素值置为1: 广度优先遍历实现: 1.初始化队列Q 2.访问顶点v:visited[v]=1;顶点v入队Q; 3.while(队列Q非空) v=队列

  • Java编程实现基于图的深度优先搜索和广度优先搜索完整代码

    为了解15puzzle问题,了解了一下深度优先搜索和广度优先搜索.先来讨论一下深度优先搜索(DFS),深度优先的目的就是优先搜索距离起始顶点最远的那些路径,而广度优先搜索则是先搜索距离起始顶点最近的那些路径.我想着深度优先搜索和回溯有什么区别呢?百度一下,说回溯是深搜的一种,区别在于回溯不保留搜索树.那么广度优先搜索(BFS)呢?它有哪些应用呢?答:最短路径,分酒问题,八数码问题等.言归正传,这里笔者用java简单实现了一下广搜和深搜.其中深搜是用图+栈实现的,广搜使用图+队列实现的,代码如下:

  • Java二叉搜索树遍历操作详解【前序、中序、后序、层次、广度优先遍历】

    本文实例讲述了Java二叉搜索树遍历操作.分享给大家供大家参考,具体如下: 前言:在上一节Java二叉搜索树基础中,我们对树及其相关知识做了了解,对二叉搜索树做了基本的实现,下面我们继续完善我们的二叉搜索树. 对于二叉树,有深度遍历和广度遍历,深度遍历有前序.中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历,如图: 因为树的定义本身就是递归定义,所以对于前序.中序以及后序这三种遍历我们使用递归的方法实现,而对于广度优先遍历需要选择其他数据结构实现,本例中我们使用队列来实现广度优先遍历.

  • Java实现二叉树的深度优先遍历和广度优先遍历算法示例

    本文实例讲述了Java实现二叉树的深度优先遍历和广度优先遍历算法.分享给大家供大家参考,具体如下: 1. 分析 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列. 深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次.要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历.中序遍历.后序遍历.具体说明如下: 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树. 中序遍历:对任一子树,先遍历其左子树,然

  • Java实现利用广度优先遍历(BFS)计算最短路径的方法

    本文实例讲述了Java实现利用广度优先遍历(BFS)计算最短路径的方法.分享给大家供大家参考.具体分析如下: 我们用字符串代表图的顶点(vertax),来模拟学校中Classroom, Square, Toilet, Canteen, South Gate, North Gate几个地点,然后计算任意两点之间的最短路径. 如下图所示: 如,我想从North Gate去Canteen, 程序的输出结果应为: BFS: From [North Gate] to [Canteen]: North Ga

  • 深度优先与广度优先Java实现代码示例

    在编程生活中,我们总会遇见树性结构,这几天刚好需要对树形结构操作,就记录下自己的操作方式以及过程.现在假设有一颗这样树,(是不是二叉树都没关系,原理都是一样的) 1.深度优先 英文缩写为DFS即Depth First Search. 深度优先搜索是一种在开发爬虫早期使用较多的方法.它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) .在一个HTML文件中,当一个超链被选择后,被链接的HTML文件将执行深度优先搜索,即在搜索其余的超链结果之前必须先完整地搜索单独的一条链.深度

  • Java实现广度优先遍历的示例详解

    目录 什么是广度优先 一个简单的例子 程序实现 总结 什么是广度优先 广度就是扩展开,广度优先的意思就是尽量扩展开.所以在算法实现的时候,就是一个循环遍历枚举每一个邻接点.其基本思路就是按层扩展,扩得越广越好. 伪代码如下: for(int i = 0; i < children.size(); i++){ children.get(i); // 调用每一个子节点 } 一个简单的例子 我们以一个简单的迷宫为例,以1代表墙,0代表路径,我们构造一个具有出入口的迷宫. 1 1 0 1 1 1 1 1

  • Java基本语法之内部类示例详解

    目录 1.内部类概念及分类 2.实例内部类 2.1实例内部类的创建 2.2使用.this和.new 2.3内部类实现迭代打印 2.4内部类的继承 3.静态内部类 4.匿名内部类 1.内部类概念及分类 将一个类定义在另一个类的内部或者接口内部或者方法体内部,这个类就被称为内部类,我们不妨将内部类所在的类称为外围类,除了定义在类,接口,方法中的内部类,还有一种特殊的内部类,那就是使用关键字new创建一个匿名类的对象,而这个匿名类其实就是一个内部类,具体说是一个匿名内部类,经常用于传入构造器实参构造对

  • Java垃圾回收机制的示例详解

    目录 一.概述 二.对象已死? 1.引用计数算法 2.可达性分析算法 3.四种引用 4.生存还是死亡? 5.回收方法区 三.垃圾收集算法 1.分代收集理论 2.名词解释 3.标记-清除算法 4.标记-复制算法 5.标记-整理算法 一.概述 说起垃圾收集(Garbage Collection,下文简称GC),有不少人把这项技术当作Java语言的伴生产 物.事实上,垃圾收集的历史远远比Java久远,在1960年诞生于麻省理工学院的Lisp是第一门开始使 用内存动态分配和垃圾收集技术的语言.当Lisp

  • java数据结构算法稀疏数组示例详解

    目录 一.什么是稀疏数组 二.场景用法 1.二维数组转稀疏数组思路 2.稀疏数组转二维数组思路 3.代码实现 一.什么是稀疏数组 当一个数组a中大部分元素为0,或者为同一个值,那么可以用稀疏数组b来保存数组a. 首先,稀疏数组是一个数组,然后以一种特定的方式来保存上述的数组a,具体处理方法: 记录数组a一共有几行几列 记录a中有多少个不同的值 最后记录不同值的元素所在行列,以及具体的值,放在一个小规模的数组里,以缩小程序的规模. 这个小规模的数组,就是稀疏数组. 举个栗子,左侧是一个二维数组,一

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

  • Go Java算法之单词规律示例详解

    目录 单词规律 方法一:哈希表(Java) 方法一:哈希表(GO) 单词规律 给定一种规律 pattern 和一个字符串 s ,判断 s 是否遵循相同的规律. 这里的 遵循 指完全匹配,例如, pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律. 示例1: 输入: pattern = "abba", s = "dog cat cat dog" 输出: true 示例 2: 输入:pattern = "abba"

  • Go Java算法之单词搜索示例详解

    目录 单词搜索 算法:DFS回溯(Java) 算法:DFS回溯(Go) 单词搜索 给定一个 m x n 二维字符网格 board 和一个字符串单词 word .如果 word 存在于网格中,返回 true :否则,返回 false . 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格.同一个单元格内的字母不允许被重复使用. 示例 1: 输入:board = [["A","B","C",&quo

  • Go java 算法之括号生成示例详解

    目录 括号生成 方法一:深度优先遍历(java) 方法一:深度优先遍历(go) 括号生成 数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合. 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <=

  • Go Java算法之累加数示例详解

    目录 累加数 方法一:穷举法(java) 方法二:深度优先遍历(go) 累加数 累加数 是一个字符串,组成它的数字可以形成累加序列. 一个有效的 累加序列 必须 至少 包含 3 个数.除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和. 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 .如果是,返回 true :否则,返回 false . 说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1

随机推荐

其他