java实现广度优先搜索算法

广度优先搜索算法(BFS)是一种用于图遍历的算法。它从图的某个节点开始,依次访问其所有邻接节点,再依次访问邻接节点的邻接节点,以此类推,直到遍历完所有节点。

BFS使用队列数据结构来实现遍历过程。具体步骤如下:

  1. 将起始节点标记为已访问,并将其加入队列。
  2. 重复以下步骤直到队列为空:
    • 从队列中取出一个节点,并访问该节点。
    • 将该节点的所有未访问邻接节点加入队列,并标记为已访问。
  3. 遍历完所有节点后,算法结束。

BFS的特点是按层遍历图,即先访问起始节点的所有邻接节点,然后访问邻接节点的邻接节点,以此类推。因此,BFS可以用来解决寻找最短路径的问题,即找到从起始节点到目标节点的最短路径。

BFS的时间复杂度为O(V+E),其中V是图的节点数,E是图的边数。

以下是使用Java实现广度优先搜索算法的示例代码:

import java.util.LinkedList;
import java.util.Queue;

class Graph {
    private int V; // 图的顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    public Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    // 添加边
    void addEdge(int v, int w) {
        adj[v].add(w);
    }

    // 广度优先搜索
    void BFS(int s) {
        boolean visited[] = new boolean[V]; // 记录顶点是否被访问过

        Queue<Integer> queue = new LinkedList<>(); // 创建队列用于广度优先搜索
        visited[s] = true; // 标记起始顶点为已访问
        queue.add(s); // 将起始顶点加入队列

        while (queue.size() != 0) {
            s = queue.poll(); // 从队列中弹出一个顶点并访问
            System.out.print(s + " ");

            // 遍历邻接表中的所有相邻顶点
            for (int i : adj[s]) {
                if (!visited[i]) {
                    visited[i] = true; // 标记相邻顶点为已访问
                    queue.add(i); // 将相邻顶点加入队列
                }
            }
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("广度优先遍历 (从顶点2开始):");
        g.BFS(2);
    }
}

在上面的示例代码中,我们首先创建了一个Graph类来表示图。Graph类中包含一个邻接表用于存储图的结构,并提供addEdge方法来添加边。

然后定义了一个BFS方法来执行广度优先搜索算法。在BFS方法中,我们使用一个boolean数组visited来记录顶点是否被访问过。我们使用一个Queue来存储待访问的顶点,起始时将起始顶点加入队列,并标记为已访问。

接下来,我们开始进行循环,直到队列为空。在每次循环中,我们从队列中弹出一个顶点s,并访问该顶点,然后遍历邻接表中的所有相邻顶点。如果相邻顶点i没有被访问过,我们将其标记为已访问,并将其加入到队列中。

最后,我们在main方法中创建一个图对象,并添加一些边来测试广度优先搜索算法。我们从顶点2开始进行广度优先遍历,并输出遍历的结果。

以上就是用Java实现广度优先搜索算法的示例代码。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/272465.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

关于 Appium 各种版本的安装,都在这里

大家在初次接触 Appium 时会看到网上各种帖子讲解如何安装 Appium&#xff0c;各种 Appium 版本的安装教程满天飞&#xff0c;而很多帖子中提供的安装教程是已经过时了的&#xff0c;容易误导初学者。 这篇文章带着你一起全面了解 Appium 各种版本如何选择如何安装。 一句话概述…

Superset 二次开发之自定义Viz Plugins(Hello World v2)

环境&#xff1a; Node.js 16npm 7 or 8安装webpack 全局安装 npm install webpack -g 安装eslint superset-frontend> npm install eslint 1.Yeoman 生成器 全局安装Yo> npm i -g yo 2.进入/superset-frontend/packages/generator-superset目录 npm i && npm…

传感器原理与应用--传感器基本特性与应变式传感器

文章目录 上一篇传感器的基本特性应变式传感器应变式传感器的应用下一篇 上一篇 传感器的基本特性 一般来说能把特定被测量信息按一定规律转换成某种可用信号的器件或装置&#xff0c;称为传感器 静态特性 灵敏度 定义&#xff1a;输出量增量 Δ y \Delta y Δy与引起输出量…

xstream 远程代码执行 CVE-2021-29505 已亲自复现

xstream 远程代码执行 CVE-2021-29505 已亲自复现 漏洞名称漏洞描述影响版本 漏洞复现环境搭建漏洞利用 修复建议总结 漏洞名称 漏洞描述 XStream 是用于将 Java 对象序列化为 XML 并再次序列化的软件。 1.4.17 之前的 XStream 版本中存在一个漏洞&#xff0c;可能允许远程攻…

集成钉钉机器人消息推送

一、简介 背景 客户需要通过钉钉接收消息通知 名词解释 群聊机器人&#xff1a;钉钉群里可以创建一个机器人&#xff0c;平台通过机器人把告警/通知推送到群里私聊机器人&#xff1a;钉钉后台开启机器人配置&#xff0c;平台绑定此机器人后&#xff0c;可以通过私聊的方式将…

C/S医院检验LIS系统源码

一、检验科LIS系统概述&#xff1a; LIS系统即实验室信息管理系统。LIS系统能实现临床检验信息化&#xff0c;检验科信息管理自动化。其主要功能是将检验科的实验仪器传出的检验数据经数据分析后&#xff0c;自动生成打印报告&#xff0c;通过网络存储在数据库中&#xff…

20231226在Firefly的AIO-3399J开发板上在Android11下调通后摄像头ov13850

20231226在Firefly的AIO-3399J开发板上在Android11下调通后摄像头ov13850 2023/12/26 8:22 开发板&#xff1a;Firefly的AIO-3399J【RK3399】 SDK&#xff1a;rk3399-android-11-r20211216.tar.xz【Android11】 Android11.0.tar.bz2.aa【ToyBrick】 Android11.0.tar.bz2.ab And…

一文搞懂类加载过程

废话不多说&#xff0c;先上一张图 1、“加载”过程做了什么&#xff1f;什么是双亲委派&#xff1f;为什么要使用双亲委派机制&#xff1f;有什么利弊&#xff1f; **加载&#xff1a;**就是将编译后的.class字节码文件【jvm只认.class文件&#xff0c;.class文件也并非只有…

C++ std::string使用效率优化

字符串操作是任何一个C开发程序无法绕过的点&#xff0c;很多时候针对字符串的操作需要进行优化&#xff0c;从而达到更优的使用效率和内存利用率。一般会采用标准的std::string替代C字符串&#xff0c;一方面是std::string为一个成熟的类对象&#xff0c;其成员操作基本能满足…

阿赵UE学习笔记——4、新建关卡

阿赵UE学习笔记目录 大家好&#xff0c;我是阿赵。   之前介绍了虚幻引擎的常用窗口功能&#xff0c;这次开始创建游戏内的世界了。首先先从创建关卡开始。 一、创建新关卡 在使用UE引擎制作游戏&#xff0c;首先要有一个场景作为基础&#xff0c;这个场景在UE里面成为关卡。…

若依(Spring boot)框架中如何在不同的控制器之间共享与使用数据

在若依框架或Spring boot框架中&#xff0c;控制器共享和使用数据是为了确保数据一致性、传递信息、提高效率和降低系统复杂性。这可以通过全局变量、依赖注入或数据库/缓存等方式实现。共享和使用数据对框架的正常运行非常关键&#xff0c;有助于促进控制器之间的协同工作&…

消息走漏提前做空腾讯爆赚30倍?逐帧分析还原真相

数量技术宅团队在CSDN学院推出了量化投资系列课程 欢迎有兴趣系统学习量化投资的同学&#xff0c;点击下方链接报名&#xff1a; 量化投资速成营&#xff08;入门课程&#xff09; Python股票量化投资 Python期货量化投资 Python数字货币量化投资 C语言CTP期货交易系统开…

C语言结构体内存对齐

文章目录 一、结构体内存对齐问题二、查看结构体成员起始位置三、设置内存对齐方式 一、结构体内存对齐问题 如下的info_s结构体类型&#xff0c;包含一个int型成员age, 一个char型成员gender, 一个int型成员id。 单从数据成员的大小进行分析&#xff0c;整个结构体的大小应为…

【JavaWeb学习笔记】18 - 文件上传下载

项目代码 https://github.com/yinhai1114/JavaWeb_LearningCode/tree/main/fileupdown 目录 文件上传 一、基本介绍 二、文件上传的基本原理 ​编辑 三、文件上传应用实例 四、文件上传的注意细节 1.解决中文乱码问题 2.分割文件夹 3.防止重名 4.百度WebUploader 5.空…

Windows无法安装edge 无法连接Internet

如果出现以上问题&#xff0c;或者Edge浏览器无法更新&#xff0c;提示防火墙错误之类的都可以解决问题。 下载以下证书文件并导入即可解决问题。 MicrosoftRootCertificateAuthority2011.cer

注意力机制(数学公式)

人类视觉注意力机制极大地提高了视觉信息处理的效率与准确性 计算机注意力机制是为了让卷积神经网络注意到他更加需要注意的地方 &#xff0c;而不是什么都关注 。 分为三种注意力机制&#xff0c;空间注意力机制&#xff0c;通道注意力机制&#xff0c;以及两者的结合。 …

关于MULTI#STORM活动利用远程访问木马瞄准印度和美国的动态情报

一、基本内容 于2023年6月22日&#xff0c;一款代号为MULTI#STORM的新网络钓鱼活动将目标瞄准了印度和美国&#xff0c;利用JavaScript文件在受感染的系统上传播远程访问木马。 二、相关发声情况 Securonix的研究人员Den luzvyk、Tim Peck和Oleg Kolesnikov发表声明称&#x…

【AI服饰】孔雀背景服装_AIGC服饰订制设计咨询产业

服饰系列 AIGC&#xff08;Artificial Intelligence Generated Content&#xff09;服饰图是指通过人工智能生成的服装设计图案。随着人工智能技术的不断进步&#xff0c;AIGC服饰图在未来有着广阔的发展空间。 首先&#xff0c;AIGC服饰图可以提供更多的设计可能性。传统的服…

PYTHON基础:K最邻近算法

K最邻近算法笔记 K最邻近算法既可以用在分类中&#xff0c;也可以用在回归中。在分类的方法&#xff0c;比如说在x-y的坐标轴上又两个成堆的数据集&#xff0c;也就是有两类&#xff0c;如果这个时候有个点在图上&#xff0c;它是属于谁&#xff1f; 原则就是哪一类离它比较近…

RK3568平台开发系列讲解(Linux系统篇)GPIO调试手段

🚀返回专栏总目录 文章目录 一、/sys/kernel/debug/gpio目录二、/sys/kernel/debug/pinctrl 目录沉淀、分享、成长,让自己和他人都能有所收获!😄 📢本篇将介绍 GPIO调试手段。 一、/sys/kernel/debug/gpio目录 debugfs 是 Linux 内核提供的一个调试文件系统,可以用于…