图论05-【无权无向】-图的广度优先BFS遍历-路径问题/检测环/二分图/最短路径问题
文章目录
- 1. 代码仓库
- 2. 单源路径
- 2.1 思路
- 2.2 主要代码
- 3. 所有点对路径
- 3.1 思路
- 3.2 主要代码
- 4. 联通分量
- 5. 环检测
- 5.1 思路
- 5.2 主要代码
- 6. 二分图检测
- 6.1 思路
- 6.2 主要代码
- 6.2.1 遍历每个联通分量
- 6.2.2 判断相邻两点的颜色是否一致
- 7. 最短路径问题
- 7.1 思路
- 7.2 代码
1. 代码仓库
https://github.com/Chufeng-Jiang/Graph-Theory
2. 单源路径
2.1 思路
- 构造visited数组和pre数组
1.1 visited数组记录当前节点是否访问过
也可以不使用visited数组,pre数组全部初始化为-1,联通的顶点对应的pre数组的值为前一个节点,pre数组中值为-1的都是不连通的顶点。
1.2 pre数组记录当前节点的前一个节点- 使用pre数组对终点进行反推回源点,并记录
- 将终点到原点的路径,反序输出
区别DFS和BFS两种解法中,递归部分参数问题。
DFS实际上是递归,把参数传进去就开始递归了。而BFS实际上是使用队列进行模拟,只需要传入源就可以,两个参数也可以但是没必要。
private void dfs(int v, int parent){ //参数一:当前顶点; 参数二:上一个顶点
private void bfs(int s){
2.2 主要代码
public SingleSourcePath(Graph G, int s){this.G = G;this.s = s;visited = new boolean[G.V()];pre = new int[G.V()];for(int i = 0; i < pre.length; i ++)pre[i] = -1;bfs(s);
}private void bfs(int s){ Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;pre[s] = s; //赋初值,源的源是源while(!queue.isEmpty()){int v = queue.remove();for(int w: G.adj(v))if(!visited[w]){queue.add(w);visited[w] = true;pre[w] = v; //w的上一个顶点是v}}
}
3. 所有点对路径
3.1 思路
对所有顶点进行遍历,创建每一个点的单源路径数组。
3.2 主要代码
public AllPairsPath_UsingSingleSourcePath(Graph G){this.G = G;paths = new SingleSourcePath[G.V()];for(int v = 0; v < G.V(); v ++)paths[v] = new SingleSourcePath(G, v);}
4. 联通分量
跟DFS是一样的
public CC(Graph G){this.G = G;visited = new int[G.V()];for(int i = 0; i < visited.length; i ++)visited[i] = -1;for(int v = 0; v < G.V(); v ++)if(visited[v] == -1){bfs(v, cccount); //从0开始cccount ++; //统计联通分量的数量}
}
5. 环检测
跟DFS也基本一样
5.1 思路
从某一点v出发,找到了点w,w被
访问过,并且w不是v的前一个节点
5.2 主要代码
public CycleDetection(Graph G){this.G = G;visited = new boolean[G.V()];pre = new int[G.V()];for(int i = 0; i < G.V(); i ++)pre[i] = -1;for(int v = 0; v < G.V(); v ++)if(!visited[v])if(bfs(v)){hasCycle = true;break;}
}// 从顶点 v 开始,判断图中是否有环
private boolean bfs(int s){Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;pre[s] = s;while(!queue.isEmpty()){int v = queue.remove();for(int w: G.adj(v))if(!visited[w]){ //如果w没有访问过queue.add(w);visited[w] = true;pre[w] = v;}else if(pre[v] != w) //从s出发,如果w被访问过,并且顶点v的前一个不是wreturn true;}return false;
}
6. 二分图检测
6.1 思路
二分图可以通过染色过程把顶点区分开,
[-1:顶点还没染色]
[0:一种颜色]
[1:另外一种颜色]
6.2 主要代码
6.2.1 遍历每个联通分量
- dfs(v, 0) 返回true代表相连的两点颜色不一样,暂未出现矛盾;
- dfs(v, 0) 返回false代表相连的两点颜色一样,不符合二分图的定义,因此进入if语句块,设置isBipartite = false;并且提前结束循环。
public BipartitionDetection(Graph G){this.G = G;visited = new boolean[G.V()];colors = new int[G.V()];for(int i = 0; i < G.V(); i ++)colors[i] = -1;for(int v = 0; v < G.V(); v ++)if(!visited[v])if(!bfs(v)){isBipartite = false;break;}}
6.2.2 判断相邻两点的颜色是否一致
private boolean bfs(int s){Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;colors[s] = 0;while(!queue.isEmpty()){int v = queue.remove();for(int w: G.adj(v))if(!visited[w]){queue.add(w);visited[w] = true;colors[w] = 1 - colors[v];}else if(colors[v] == colors[w])return false;}return true;}
7. 最短路径问题

7.1 思路
- 引入dis数组;
- 在从出发顶点进行BFS的时,pre数组记录当前节点的上一个节点,dis数组更新为
当前节点到源点的距离=上一个节点到出发点的距离+1。
private int[] dis;
dis[w] = dis[v] + 1;
7.2 代码
public USSSPath(Chapt04_BFS_Path._0402_SingleSourcePath.Graph G, int s){this.G = G;this.s = s;visited = new boolean[G.V()];pre = new int[G.V()];dis = new int[G.V()];for(int i = 0; i < pre.length; i ++) {pre[i] = -1;dis[i] = -1;}bfs(s);for (int i = 0; i < G.V(); i++) {System.out.print(dis[i] + " ");}System.out.println();
}private void bfs(int s){ // 区分一下DFS两个参数,DFS实际上是递归,把参数传进去就开始递归了。而BFS实际上是使用队列进行模拟,只需要传入源就可以,两个参数也可以但是没必要Queue<Integer> queue = new LinkedList<>();queue.add(s);visited[s] = true;pre[s] = s; //赋初值,源的源是源dis[s] = 0;while(!queue.isEmpty()){int v = queue.remove();for(int w: G.adj(v))if(!visited[w]){queue.add(w);visited[w] = true;pre[w] = v; //w的上一个顶点是vdis[w] = dis[v] + 1;}}
}

相关文章:
图论05-【无权无向】-图的广度优先BFS遍历-路径问题/检测环/二分图/最短路径问题
文章目录 1. 代码仓库2. 单源路径2.1 思路2.2 主要代码 3. 所有点对路径3.1 思路3.2 主要代码 4. 联通分量5. 环检测5.1 思路5.2 主要代码 6. 二分图检测6.1 思路6.2 主要代码6.2.1 遍历每个联通分量6.2.2 判断相邻两点的颜色是否一致 7. 最短路径问题7.1 思路7.2 代码 1. 代码…...
uniapp:谷歌地图,实现地图展示,搜索功能,H5导航
页面展示 APP H5 谷歌地图功能记录,谷歌key申请相对复杂一些,主要需要一些国外的身份信息。 1、申请谷歌key 以下是申请谷歌地图 API 密钥的流程教程: 登录谷歌开发者控制台:打开浏览器,访问 Google Cloud Platform Console。 1、创建或选择项目:如果你还没有创建项目…...
关于腾讯云轻量应用服务器性能测评,看这一篇文章就够了
腾讯云轻量应用服务器性能如何?为什么便宜是不是性能不行?腾讯云百科txybk.com从轻量应用服务器的CPU型号、处理器主频、内存、公网带宽、月流量和系统盘多方面来详细测评轻量性能,轻量应用服务器性价比高,并不是性能不行…...
HDFS集群NameNode高可用改造
文章目录 背景高可用改造方案实施环境准备配置文件修改应用配置集群状态验证高可用验证 背景 假定目前有3台zookeeper服务器,分别为zk-01/02/03,DataNode服务器若干; 目前HDFS集群的Namenode没有高可用配置,Namenode和Secondary…...
Spark集群中一个Worker启动失败的排错记录
文章目录 1 检查失败节点worker启动日志2 检查正常节点worker启动日志3 查看正常节点spark环境配置4 又出现新的ERROR4.1 报错解释4.2 报错解决思路4.3 端口报错解决操作 集群下电停机后再次启动时,发现其中一台节点的worker启动失败。 1 检查失败节点worker启动日…...
Mysql的JDBC知识点
什么是JDBC JDBC(Java DataBase Connectivity) 称为Java数据库连接,它是一种用于数据库访问的应用程序API,由一组用Java语言编写的类和接口组成,有了JDBC就可以用统一的语法对多种关系数据库进行访问,而不用担心其数据库操作语…...
git的实际操作
文章目录 删除GitHub上的某个文件夹克隆仓库到另一个仓库 删除GitHub上的某个文件夹 克隆仓库到另一个仓库 从原地址克隆一份裸板仓库 –bare创建的克隆版本库都不包含工作区,直接就是版本库的内容,这样的版本库称为裸版本库 git clone --bare ****(原…...
数据结构零基础C语言版 严蔚敏-线性表、顺序表
二、顺序表和链表 1. 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串...... 线性表在逻辑上是线性结构,…...
Keil uVision 5 MDK版软件安装包下载及安装教程(最详细图文教程)
目录 一.简介 二.安装步骤 软件:Keil uvision5版本:MDKv518语言:中文/英文大小:377.01M安装环境:Win11/Win10/Win8/Win7硬件要求:CPU2.59GHz 内存4G(或更高)下载通道①百度网盘丨64位下载链接…...
单目3D目标检测[基于深度辅助篇]
基于深度辅助的方法 1. Pseudo-LiDAR Pseudo-LiDAR from Visual Depth Estimation: Bridging the Gap in 3D Object Detection for Autonomous Driving康奈尔大学https://zhuanlan.zhihu.com/p/52803631 首先利用DRON或PSMNET从单目 (Monocular)或双目 (Stereo)图像获取对应的…...
Ubuntu20.04下安装MySQL8环境
Ubuntu20.04下安装MySQL8环境 1.下载MySQL客户端和服务器2.配置MySQL3.测试MySQL4.设置MySQL服务开机自启动5.修改root密码MySQL数据库基本使用启动MySQL数据库服务重启MySQL数据库服务停止MySQL数据库服务查看MySQL运行状态设置MySQL服务开机自启动停止MySQL服务开机自启动MyS…...
html鼠标悬停图片放大
要在HTML中实现鼠标悬停时图片放大的效果,你可以使用CSS和JavaScript来完成。下面是一个简单的示例: 首先,创建一个HTML文档,包含一张图片和相应的CSS和JavaScript代码。 <!DOCTYPE html> <html lang"en">…...
基于hugging face的autogptq量化实践
1.量化并保存到本地的 #导入库: from transformers import AutoModelForCausalLM, AutoTokenizer, GPTQConfig model_id "facebook/opt-125m"quantization_config GPTQConfig(bits4,group_size128,dataset"c4",desc_actFalse, )tokenizer A…...
MySQL2:MySQL中一条查询SQL是如何执行的?
MySQL2:MySQL中一条查询SQL是如何执行的? MySQL中一条查询SQL是如何执行的?1.连接怎么查看MySQL当前有多少个连接?思考:为什么连接数是查看线程?客户端的连接和服务端的线程有什么关系?MySQL参数…...
C++入门01—从hello word!开始
1.第一个C程序 1.1 创建项目 第一次使用Visual Studio时: 1.2 创建文件 1.3 编写代码 编写第一个代码: #include<iostream> using namespace std; int main() {cout << "hello word!" << endl;system("pause"…...
Mingw下载---运行vscodeC++文件
下载 下载网址: https://sourceforge.net/projects/mingw-w64/files/mingw-w64/mingw-w64-release/ 翻到最下面,选择win64的安装: 下载完,解压到没有空格和中文字符的路径。不然在vscode中运行不了C代码。...
数据安全与PostgreSQL:最佳保护策略
在当今数字化时代,数据安全成为了企业不可或缺的一环。特别是对于使用数据库管理系统(DBMS)的组织来说,确保数据的完整性、保密性和可用性至关重要。在众多DBMS中,PostgreSQL作为一个强大而灵活的开源数据库系统&#…...
火山引擎实时、低延时拥塞控制算法的优化实践
摘要 火山引擎智能拥塞控制算法 VICC(Volcano Intelligent Congestion Control)是一种自适应的拥塞控制算法,旨在解决全球不同网络环境下,不同音视频应用对带宽利用率和延时的差异化要求。它结合了传统拥塞控制算法(如…...
adb设备调试常用命令
自从工作越来越忙后,越来越懒得写文章了,趁着1024程序员节,仪式性地写篇文章,分享一下最近调试设备经常用到的adb指令~ 1.查看应用内存占用 1.1 dumpsys meminfo package dumpsys是查看系统服务信息的一个常用指令,可…...
ubuntu下Docker的简单使用并利用主机显示
首先分享一个docker镜像的网站:https://hub.docker.com/search?q 这个网站里面有很多配置好的镜像,可以直接拉取。 下面介绍一下docker的安装和使用。 1、docker得到安装: sudo apt-get install docker 2、docker拉取一个镜像到本地,这里我…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
网络编程(UDP编程)
思维导图 UDP基础编程(单播) 1.流程图 服务器:短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
