图论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 方法 解决问题的步骤采用如下方式: 基本的,已知元素…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
golang循环变量捕获问题
在 Go 语言中,当在循环中启动协程(goroutine)时,如果在协程闭包中直接引用循环变量,可能会遇到一个常见的陷阱 - 循环变量捕获问题。让我详细解释一下: 问题背景 看这个代码片段: fo…...
基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真
目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销,平衡网络负载,延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
CMake控制VS2022项目文件分组
我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...
