当前位置: 首页 > news >正文

图论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 思路

  1. 构造visited数组和pre数组
    1.1 visited数组记录当前节点是否访问过
    也可以不使用visited数组,pre数组全部初始化为-1,联通的顶点对应的pre数组的值为前一个节点,pre数组中值为-1的都是不连通的顶点。
    1.2 pre数组记录当前节点的前一个节点
  2. 使用pre数组对终点进行反推回源点,并记录
  3. 将终点到原点的路径,反序输出

区别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 遍历每个联通分量

  1. dfs(v, 0) 返回true代表相连的两点颜色不一样,暂未出现矛盾;
  2. 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 思路

  1. 引入dis数组;
  2. 在从出发顶点进行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、创建或选择项目:如果你还没有创建项目…...

关于腾讯云轻量应用服务器性能测评,看这一篇文章就够了

腾讯云轻量应用服务器性能如何&#xff1f;为什么便宜是不是性能不行&#xff1f;腾讯云百科txybk.com从轻量应用服务器的CPU型号、处理器主频、内存、公网带宽、月流量和系统盘多方面来详细测评轻量性能&#xff0c;轻量应用服务器性价比高&#xff0c;并不是性能不行&#xf…...

HDFS集群NameNode高可用改造

文章目录 背景高可用改造方案实施环境准备配置文件修改应用配置集群状态验证高可用验证 背景 假定目前有3台zookeeper服务器&#xff0c;分别为zk-01/02/03&#xff0c;DataNode服务器若干&#xff1b; 目前HDFS集群的Namenode没有高可用配置&#xff0c;Namenode和Secondary…...

Spark集群中一个Worker启动失败的排错记录

文章目录 1 检查失败节点worker启动日志2 检查正常节点worker启动日志3 查看正常节点spark环境配置4 又出现新的ERROR4.1 报错解释4.2 报错解决思路4.3 端口报错解决操作 集群下电停机后再次启动时&#xff0c;发现其中一台节点的worker启动失败。 1 检查失败节点worker启动日…...

Mysql的JDBC知识点

什么是JDBC JDBC(Java DataBase Connectivity) 称为Java数据库连接&#xff0c;它是一种用于数据库访问的应用程序API&#xff0c;由一组用Java语言编写的类和接口组成&#xff0c;有了JDBC就可以用统一的语法对多种关系数据库进行访问&#xff0c;而不用担心其数据库操作语…...

git的实际操作

文章目录 删除GitHub上的某个文件夹克隆仓库到另一个仓库 删除GitHub上的某个文件夹 克隆仓库到另一个仓库 从原地址克隆一份裸板仓库 –bare创建的克隆版本库都不包含工作区&#xff0c;直接就是版本库的内容&#xff0c;这样的版本库称为裸版本库 git clone --bare ****(原…...

数据结构零基础C语言版 严蔚敏-线性表、顺序表

二、顺序表和链表 1. 线性表 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串...... 线性表在逻辑上是线性结构&#xff0c;…...

Keil uVision 5 MDK版软件安装包下载及安装教程(最详细图文教程)

目录 一.简介 二.安装步骤 软件&#xff1a;Keil uvision5版本&#xff1a;MDKv518语言&#xff1a;中文/英文大小&#xff1a;377.01M安装环境&#xff1a;Win11/Win10/Win8/Win7硬件要求&#xff1a;CPU2.59GHz 内存4G(或更高&#xff09;下载通道①百度网盘丨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中实现鼠标悬停时图片放大的效果&#xff0c;你可以使用CSS和JavaScript来完成。下面是一个简单的示例&#xff1a; 首先&#xff0c;创建一个HTML文档&#xff0c;包含一张图片和相应的CSS和JavaScript代码。 <!DOCTYPE html> <html lang"en">…...

基于hugging face的autogptq量化实践

1.量化并保存到本地的 #导入库&#xff1a; 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&#xff1a;MySQL中一条查询SQL是如何执行的&#xff1f; MySQL中一条查询SQL是如何执行的&#xff1f;1.连接怎么查看MySQL当前有多少个连接&#xff1f;思考&#xff1a;为什么连接数是查看线程&#xff1f;客户端的连接和服务端的线程有什么关系&#xff1f;MySQL参数…...

C++入门01—从hello word!开始

1.第一个C程序 1.1 创建项目 第一次使用Visual Studio时&#xff1a; 1.2 创建文件 1.3 编写代码 编写第一个代码&#xff1a; #include<iostream> using namespace std; int main() {cout << "hello word!" << endl;system("pause"…...

Mingw下载---运行vscodeC++文件

下载 下载网址&#xff1a; https://sourceforge.net/projects/mingw-w64/files/mingw-w64/mingw-w64-release/ 翻到最下面&#xff0c;选择win64的安装&#xff1a; 下载完&#xff0c;解压到没有空格和中文字符的路径。不然在vscode中运行不了C代码。...

数据安全与PostgreSQL:最佳保护策略

在当今数字化时代&#xff0c;数据安全成为了企业不可或缺的一环。特别是对于使用数据库管理系统&#xff08;DBMS&#xff09;的组织来说&#xff0c;确保数据的完整性、保密性和可用性至关重要。在众多DBMS中&#xff0c;PostgreSQL作为一个强大而灵活的开源数据库系统&#…...

火山引擎实时、低延时拥塞控制算法的优化实践

摘要 火山引擎智能拥塞控制算法 VICC&#xff08;Volcano Intelligent Congestion Control&#xff09;是一种自适应的拥塞控制算法&#xff0c;旨在解决全球不同网络环境下&#xff0c;不同音视频应用对带宽利用率和延时的差异化要求。它结合了传统拥塞控制算法&#xff08;如…...

adb设备调试常用命令

自从工作越来越忙后&#xff0c;越来越懒得写文章了&#xff0c;趁着1024程序员节&#xff0c;仪式性地写篇文章&#xff0c;分享一下最近调试设备经常用到的adb指令~ 1.查看应用内存占用 1.1 dumpsys meminfo package dumpsys是查看系统服务信息的一个常用指令&#xff0c;可…...

ubuntu下Docker的简单使用并利用主机显示

首先分享一个docker镜像的网站&#xff1a;https://hub.docker.com/search?q 这个网站里面有很多配置好的镜像&#xff0c;可以直接拉取。 下面介绍一下docker的安装和使用。 1、docker得到安装&#xff1a; sudo apt-get install docker 2、docker拉取一个镜像到本地,这里我…...

云启出海,智联未来|阿里云网络「企业出海」系列客户沙龙上海站圆满落地

借阿里云中企出海大会的东风&#xff0c;以**「云启出海&#xff0c;智联未来&#xff5c;打造安全可靠的出海云网络引擎」为主题的阿里云企业出海客户沙龙云网络&安全专场于5.28日下午在上海顺利举办&#xff0c;现场吸引了来自携程、小红书、米哈游、哔哩哔哩、波克城市、…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

全面解析数据库:从基础概念到前沿应用​

在数字化时代&#xff0c;数据已成为企业和社会发展的核心资产&#xff0c;而数据库作为存储、管理和处理数据的关键工具&#xff0c;在各个领域发挥着举足轻重的作用。从电商平台的商品信息管理&#xff0c;到社交网络的用户数据存储&#xff0c;再到金融行业的交易记录处理&a…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...