算法-图-数据结构(邻接矩阵)-BFS广度优先遍历
邻接矩阵广度优先遍历(BFS)是一种用于遍历或搜索图的算法,以下是具体介绍:
1. 基本概念
图是一种非线性的数据结构,由顶点和边组成,可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数据结构,是一个二维数组,其中行和列都对应图中的顶点。如果顶点i与顶点j之间存在一条边,则矩阵的第i行第j列的元素为1;否则为0[^4^]。
广度优先搜索是一种遍历或搜索图的算法,它按照从根节点到最远节点的层次顺序进行搜索。在邻接矩阵中,BFS可以使用队列实现。
2. 算法步骤
2.1 初始化队列,用于存储待访问的节点,并将起点加入队列。
2.1 标记已访问节点,通常使用一个数组来记录每个节点是否已被访问过,以避免重复访问。
2.3从队列中取出一个节点,检查该节点是否为目标节点。如果是,则搜索结束;如果不是,将其所有未访问的邻接节点加入队列,并标记为已访问。
重复步骤3,直到队列为空或找到目标节点
3.算法实现
图数据结构定义
package com.example.demo;
//邻接矩阵广度优先遍历
public class YuGraph {private String[] v;private int[][] vG;//默认空构造YuGraph(){}//初始赋值构造YuGraph(String[] v,int [][] vG ){this.v=v;this.vG=vG;}public String[] getV() {return v;}public void setV(String[] v) {this.v = v;}public int[][] getvG() {return vG;}public void setvG(int[][] vG) {this.vG = vG;}
}
BFS算法实现
package com.example.demo;import java.util.ArrayDeque;
import java.util.List;
import java.util.Queue;//广度优先遍历
public class YuTestBFS {//插入变的关系public static void insertBian(int [][] a, int i,int j){a[i][j]=1;}public static void bfsCreate(){//创建顶点String[] v=new String[]{"A","B","C","D","E"};//创建边int [][] vG=new int[v.length][v.length];//插入ab,bc,be,cdinsertBian(vG,0,1);//bcinsertBian(vG,1,2);//beinsertBian(vG,1,4);//cdinsertBian(vG,2,3);//创建邻接矩阵YuGraph graph=new YuGraph(v,vG);//打印结果System.out.println("顶点");for(int i=0;i<graph.getV().length;i++){System.out.print(graph.getV()[i]);System.out.print(" ");}System.out.println();System.out.println("邻接矩阵");for(int i=0;i<graph.getvG().length;i++){for(int j=0;j<graph.getV().length;j++){System.out.print(graph.getvG()[i][j]);System.out.print(" ");}System.out.println();}//BFS访问实现//1.定义访问标记列表boolean [] flagArr=new boolean[v.length];for(int i=0;i<v.length;i++){flagArr[i]=false;}//2.定义辅助队列Queue<Integer> queue=new ArrayDeque<>();//A顶点入队queue.offer(0);flagArr[0]=true;System.out.print("BFS广度优先访问顶点:");System.out.print(v[0]);System.out.print(" ");//当队列不为空,逐层访问while (!queue.isEmpty()){//对头出队int vHead= queue.poll();//访问队头所在的邻接矩阵for(int i=0;i<v.length;i++){if(graph.getvG()[vHead][i]==1&&flagArr[i]==false){//访问System.out.print("访问 ");System.out.print(v[i]);System.out.print(" ");flagArr[i]=false;//被访问的点入队queue.offer(i);}}}}public static void main(String[] args) {bfsCreate();}
}
结果样例

相关文章:
算法-图-数据结构(邻接矩阵)-BFS广度优先遍历
邻接矩阵广度优先遍历(BFS)是一种用于遍历或搜索图的算法,以下是具体介绍: 1. 基本概念 图是一种非线性的数据结构,由顶点和边组成,可分为无向图、有向图、加权图、无权图等。邻接矩阵是表示图的一种数…...
数学建模之数学模型—2:非线性规划
文章目录 非线性规划基本概念与结论凸集与凸函数极值条件无约束条件的极值判断条件有约束条件的极值判断条件 无约束非线性规划一维搜索算法步骤示例特点代码模板 最速下降法算法详细步骤 代码实现示例最优步长的求解 黄金分割法斐波那契法牛顿法阻尼牛顿法模式搜索法Powell方法…...
unity学习51:所有UI的父物体:canvas画布
目录 1 下载资源 1.1 在window / Asset store下下载一套免费的UI资源 1.2 下载,导入import 1.3 导入后在 project / Asset下面可以看到 2 画布canvas,UI的父物体 2.1 创建canvas 2.1.1 画布的下面是 event system是UI相关的事件系统 2.2 canvas…...
ctfshow做题笔记—栈溢出—pwn57~pwn60
目录 前言 一、pwn57(先了解一下简单的64位shellcode吧) 二、pwn58 三、pwn59(64位 无限制) 四、pwn60(入门难度shellcode) 前言 往前写了几道题,与shellcode有关,关于shellc…...
数据结构 1-2 线性表的链式存储-链表
1 原理 顺序表的缺点: 插入和删除移动大量元素数组的大小不好控制占用一大段连续的存储空间,造成很多碎片 链表规避了上述顺序表缺点 逻辑上相邻的两个元素在物理位置上不相邻 头结点 L:头指针 头指针:链表中第一个结点的存储…...
ArcGIS Pro进行坡度与坡向分析
在地理信息系统中,坡度分析是一项至关重要的空间分析方法,旨在精确计算地表或地形的坡度,为地形特征识别、土地资源规划、环境保护、灾害预警等领域提供科学依据。本文将详细介绍如何利用ArcGIS Pro这一强大的地理信息系统软件,进…...
My first Android application
界面元素组成: 功能代码: /*实现功能:当输入内容后,欢迎文本发生相应改变,并清除掉文本域内容当未输入任何内容时,弹出提示文本以警告用户*/val greetingText findViewById<TextView>(R.id.printer)…...
ZLMediaKi集群设置
要在集群环境中部署 ZLMediaKit,您可以按照以下步骤进行操作。ZLMediaKit 是一个高性能的流媒体服务器,支持 RTMP、RTSP、HLS 等协议。以下是一个详细的集群部署方案: ### 1. 环境准备 - **服务器**:准备多台服务器,…...
Docker基础实践与应用举例
Docker 是一个轻量级容器化平台,通过将应用及其依赖打包到容器中,实现快速部署和环境一致性。以下是 Docker 的实践与应用场景举例,结合具体操作步骤: 一、基础实践 1. 快速启动一个容器 # 运行一个Nginx容器,映射宿…...
Innovus中快速获取timing path逻辑深度的golden脚本
在实际项目中我们经常会遇到一条timing path级数特别多,可能是一两页都翻不完。此时,我们大都需要手工去数这条path上到底有哪些是设计本身的逻辑,哪些是PR工具插入的buffer和inverter。 数字IC后端手把手培训教程 | Clock Gating相关clock …...
百度AI图片助手,免费AI去水印、画质修复、画面延展以及局部替换
最近,要是你常用百度图片,可能已经发现了它新添的一个超实用功能——百度AI图片助手。但很多朋友不知道它的入口地址,我们今天给大家分享一下。 这个功能的出现,在图片编辑修改方面带来了极大便利,它涵盖了AI去水印、…...
【前端】Axios AJAX Fetch
不定期更新,建议关注收藏点赞。 目录 AxiosAJAXCORS 允许跨域请求 Fetch Axios axios 是一个基于 Promise 的 JavaScript HTTP 客户端,用于浏览器和 Node.js 中发送 HTTP 请求。它提供了一个简单的 API 来发起请求,并处理请求的结果。axios …...
测试面试题:以一个登录窗口为例,设计一下登录界面测试的思路和方法
在测试登录窗口时,可以从 表单测试、 逻辑判断和 业务流程三个方面设计测试思路和方法。以下是一个详细的测试方案: 1. 表单测试 表单测试主要关注输入框、按钮等UI元素的正确性和用户体验。 测试点: 输入框测试 用户名和密码输入框是否正常显示。输入框是否支持预期的字符类…...
Android之图片保存相册及分享图片
文章目录 前言一、效果图二、实现步骤1.引入依赖库2.二维码生成3.布局转图片保存或者分享 总结 前言 其实现在很多分享都是我们自定义的,更多的是在界面加了很多东西,然后把整个界面转成图片保存相册和分享,而且现在分享都不需要第三方&…...
EX_25/2/24
写一个三角形类,拥有私有成员 a,b,c 三条边 写好构造函数初始化 abc 以及 abc 的set get 接口 再写一个等腰三角形类,继承自三角形类 1:写好构造函数,初始化三条边 2:要求无论如何,等腰三角形类对象&#x…...
ElasticSearch公共方法封装
业务场景 1、RestClientBuilder初始化(同时支持单机与集群) 2、发送ES查询请求公共方法封装(支持sql、kql、代理访问、集群访问、鉴权支持) 3、判断ES索引是否存在(/_cat/indices/${indexName}) 4、判断ES…...
JVM之JVM的组成
Java 虚拟机(JVM)是 Java 程序的运行核心,它主要由类加载系统、运行时数据区、执行引擎和本地方法接口这几个关键部分组成。 类加载系统(Class Loading System) 类加载系统负责在程序运行时动态地将 Java 类加载到 J…...
贪心算法
int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题 为一个小老鼠准备了M磅的猫粮,准备去和看守仓库的猫做交易,因为仓库里有小老鼠喜欢吃的五香豆,第i个房间有J[i] 磅的五香豆…...
Linux下安装中文输入法总结
Linux下安装中文输入法总结_linux 微软拼音-CSDN博客文章浏览阅读4.2w次,点赞21次,收藏92次。众所周知,fcitx和ibus是两款很好用的Linux中文输入法框架。下面来说一下其安装方法以及会踩的坑。首先fcitx和ibus是不能共存的,两者只…...
人工智能(AI):科技新纪元的领航者
摘要 人工智能(AI)作为当今科技领域最具变革性的力量之一,正以惊人的速度重塑着我们的世界。本文旨在全面且专业地介绍人工智能,涵盖其定义、发展历程、关键技术、应用领域、面临的挑战以及未来展望等方面,以期为读者…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
JavaScript 中的 ES|QL:利用 Apache Arrow 工具
作者:来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗?了解下一期 Elasticsearch Engineer 培训的时间吧! Elasticsearch 拥有众多新功能,助你为自己…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
AI语音助手的Python实现
引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
