图论04-【无权无向】-图的广度优先遍历
文章目录
- 1. 代码仓库
- 2. 广度优先遍历图解
- 3.主要代码
- 4. 完整代码
1. 代码仓库
https://github.com/Chufeng-Jiang/Graph-Theory
2. 广度优先遍历图解

3.主要代码
- 原点入队列
- 原点出队列的同时,将与其相邻的顶点全部入队列
- 下一个顶点出队列
- 出队列的同时,将与其相邻的顶点全部入队列
private void bfs(int s){ //使用循环Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;while(!queue.isEmpty()){ //只要不是空就不停地出队int v = queue.remove(); // v记录队首元素 | 相邻顶点入队后,重新进入while循环,队首出队order.add(v); //添加到order数组中,order数组装的是按照BFS顺序遍历的顶点for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相邻的顶点入队列visited[w] = true;}}
}
复杂度:O(V+E)
4. 完整代码
输入文件
7 9
0 1
0 3
1 2
1 6
2 3
2 5
3 4
4 5
5 6
package Chapt04_BFS_Path._0401_Graph_BFS_Queue;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;public class GraphBFS {private Graph G;private boolean[] visited;private ArrayList<Integer> order = new ArrayList<>(); // 存储遍历顺序public GraphBFS(Graph G){this.G = G;visited = new boolean[G.V()];//遍历所有连通分量for(int v = 0; v < G.V(); v ++)if(!visited[v])bfs(v);}private void bfs(int s){ //使用循环Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;while(!queue.isEmpty()){ //只要不是空就不停地出队int v = queue.remove(); // v记录队首元素 | 相邻顶点入队后,重新进入while循环,队首出队order.add(v); //添加到order数组中,order数组装的是按照BFS顺序遍历的顶点for(int w: G.adj(v))if(!visited[w]){queue.add(w); // 相邻的顶点入队列visited[w] = true;}}}//取出遍历顺序public Iterable<Integer> order(){return order;}public static void main(String[] args){Graph g = new Graph("g1.txt");GraphBFS graphBFS = new GraphBFS(g);System.out.println("BFS Order : " + graphBFS.order());}
}

相关文章:
图论04-【无权无向】-图的广度优先遍历
文章目录 1. 代码仓库2. 广度优先遍历图解3.主要代码4. 完整代码 1. 代码仓库 https://github.com/Chufeng-Jiang/Graph-Theory 2. 广度优先遍历图解 3.主要代码 原点入队列原点出队列的同时,将与其相邻的顶点全部入队列下一个顶点出队列出队列的同时,将…...
layui的一些问题
为什么table.render, ins1.config有时候获取的值是上一次的?例如ins1.conf.page.curr? 这是一段table.render代码 let ins1 table.render({...})一般情况下ins1.conf可以获得表格的当前页,页数等;但是有时候获得的页数是上一次的;主要是因为在table.reload后没有继续赋值的…...
设计模式_中介者模式
中介者模式 介绍 设计模式定义案例问题堆积在哪里解决办法中介者代替了多个对象之间的互动 使对象1 2 3 之间的互动 变为: 对象1->中介 对象2->中介 对象3->中介好友之间 约饭好友1 通知 好友2 -3 -4 等等加一个群 谁想吃饭就 通知一下 类图 代码 角色 …...
062:mapboxGL通过jumpTo方式跳转到某位置
第062个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中通过jumpTo方式跳转到某位置。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共122行)相关API参考:专栏目标示例效果 配置方式 1)查看基础设置…...
学成在线第一天-课程内容管理服务搭建以及查询课程接口设计
目录 一、搭建课程内容管理服务 二、设计接口 三、面试题 四、总结 一、搭建课程内容管理服务 没什么好说的,直接就是创建内容模块 然后这个继承父模块,然后再课程内容模块下面创建三个子模块,model、sevice、controller model依赖base…...
4.7 IP多播
思维导图: **4.7.1 IP多播的基本概念** --- **1. 定义和背景** - IP多播:从一个源点发送信息至多个终点的技术。 - 1988年:Steve Deering首次提及IP多播。 - 1992年:IETF进行了首次IP多播试验,当时有20个网点参与。 …...
XML与html解析,区别,如何使用
目录 简介: HTML(超文本标记语言): 如何使用HTML: XML(可扩展标记语言): 如何使用XML: 区别: 简介: XML(可扩展标记语言)和 HTMLÿ…...
【广州华锐互动】利用VR开展建筑塔吊安全操作学习的好处?
随着科技的不断发展,虚拟现实(VR)技术已经逐渐渗透到各个领域,为人们的生活带来了前所未有的便利。在工程教育领域,VR建筑塔吊安全操作学习作为一种新型的教学手段,正逐渐成为提高教学质量和培养高素质工程…...
分享一下怎么开发一个陪诊小程序
开发一个陪诊小程序需要综合考虑许多方面,包括但不限于市场需求、用户体验、技术实现和运营策略。以下是一篇以开发陪诊小程序为主题的文章。 一、背景介绍 随着社会的发展和人口老龄化的加剧,越来越多的老年人、病患和孕妇需要就医,而由于各…...
从一道面试题开始学习C++标准库提供的并发编程工具
一个空列表,用两个函数(只可调用一次)轮流写入值(一个写奇数,一个写偶数), 最终实现列表的值为1-100,有序排列。 简单分析:假设这两个函数分别为A和B,A函数往…...
第三章 内存管理 十三、页面置换算法(最佳置换算法、先进先出置换算法、最近最久未使用置换算法、时钟置换算法、改进型的时钟置换算法)
目录 一、定义 二、分类 1、最佳置换算法 / 最远置换算法(OPT,Optimal): 1.1、定义: 1.2、例子: 2、先进先出置换算法(FIFO): 2.1、定义: 2.2、实现方法: 2.3、例子: 3、最…...
连接到EC2,开启root登录
1.启动完新实例,下载密钥对密钥对登录 ssh -i "ec2-user.pem" ec2-userec2-xx-xx-xx-xx.compute-1.amazonaws.com2.为root设置密码 sudo passwd root3.切换到root权限 su root4.修改ssh配置文件,允许密码登陆 vi /etc/ssh/sshd_config Pas…...
线性代数-Python-02:矩阵的基本运算 - 手写Matrix及numpy中的用法
文章目录 一、代码仓库二、矩阵的基本运算2.1 矩阵的加法2.2 矩阵的数量乘法2.3 矩阵和向量的乘法2.4 矩阵和矩阵的乘法2.5 矩阵的转置 三、手写Matrix代码Matrix.pymain_matrix.pymain_numpy_matrix.py 一、代码仓库 https://github.com/Chufeng-Jiang/Python-Linear-Algebra-…...
6.MySQL内置函数
个人主页:Lei宝啊 愿所有美好如期而遇 日期函数 current_date() 当前日期 select 可以做表达式和函数的计算。 current_time() 当前时间 current_timestamp() 当前日期加时间 注意:值得说明的是这三个函数底层调用的都是同一个函数,只不…...
3dmax中导出模型到unity注意事项
从3dmax中导出 1. 注意单位,根据需要,选英寸还是选厘米 2. 不能导出有错误的骨骼,否则导入后模型网格里出现 Skinned Mesh Renderer ,对网格变换移动有影响,正常情况下都应该是 Mesh Renderer 3. 导出一般不带光源和…...
QTday05(TCP的服务端客户端通信)
实现聊天室功能 服务端代码: pro文件需要导入 network 头文件: #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QTcpServer>//服务端 #include <QTcpSocket>//客户端 #include <QList> #include <QMes…...
【MATLAB源码-第52期】基于matlab的4用户DS-CDMA误码率仿真,对比不同信道以及不同扩频码。
操作环境: MATLAB 2022a 1、算法描述 1. DS-CDMA系统 DS-CDMA (Direct Sequence Code Division Multiple Access) 是一种多址接入技术,其基本思想是使用伪随机码序列来调制发送信号。DS-CDMA的特点是所有用户在同一频率上同时发送和接收信息…...
Spring 路径与占位符
SpringMVC支持ant风格的路径 ?:表示任意的单个字符 *:表示任意的0个或多个字符 \**:表示任意的一层或多层目录 注意:在使用**时,只能使用/**/xxx的方式 1.测试 ? <a th:href"{/succe…...
MIT 6.824 -- Cache Consistency -- 11
MIT 6.824 -- Cache Consistency -- 11 引言严峻挑战锁服务缓存一致性问题案例演示优化 原子性问题故障恢复问题log内容故障恢复 小结 课程b站视频地址: MIT 6.824 Distributed Systems Spring 2020 分布式系统 推荐伴读读物: 极客时间 – 大数据经典论文解读DDIA – 数据密集…...
Python在列表中如何对多个参数进行修改
1 问题 在python中经常会使用到列表,列表是常见的一种数据类型。对于一个庞大的列表,要调取列表中的对象,应如何快速准确的调取或快速的调取多个对象? 2 方法 解决问题的步骤采用如下方式: 基本的,已知元素…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
MFC内存泄露
1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
家政维修平台实战20:权限设计
目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系,主要是分成几个表,用户表我们是记录用户的基础信息,包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题,不同的角色…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
数据库分批入库
今天在工作中,遇到一个问题,就是分批查询的时候,由于批次过大导致出现了一些问题,一下是问题描述和解决方案: 示例: // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...
汇编常见指令
汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX(不访问内存)XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...
