图论03-【无权无向】-图的深度优先遍历-路径问题/检测环/二分图
文章目录
- 1. 代码仓库
- 2. 单源路径
- 2.1 思路
- 2.2 主要代码
- 3. 所有点对路径
- 3.1 思路
- 3.2 主要代码
- 4. 路径问题的优化-提前结束递归
- 4.1 思路
- 4.2 主要代码
- 5. 检测环
- 5.1 思路
- 5.2 主要代码
- 5. 二分图
- 5.1 思路
- 5.2 主要代码
- 5.2.1 遍历每个联通分量
- 5.2.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数组对终点进行反推回源点,并记录
- 将终点到原点的路径,反序输出
2.2 主要代码
public SingleSourcePath(Graph G, int s){ //单源路径,要把源s传进来,而且只考虑与s连通的顶点,不连通的不考虑G.validateVertex(s);this.G = G;this.s = s;visited = new boolean[G.V()];pre = new int[G.V()];dfs(s, s);}private void dfs(int v, int parent){ //参数一:当前顶点; 参数二:上一个顶点visited[v] = true;pre[v] = parent;for(int w: G.adj(v)) //跟v相邻的所有顶点,相当于v是源,遍历与当前顶点相邻的所有点if(!visited[w])dfs(w, v); //(顶点,源)}public Iterable<Integer> path(int t){ //从源到t的路径ArrayList<Integer> res = new ArrayList<Integer>();if(!isConnectedTo(t)) return res; int cur = t; // 从t往回找while(cur != s){res.add(cur); //添加当前节点(循环内不包含源)cur = pre[cur]; //pre[cur]的值是cur的上一个节点}res.add(s); //添加源Collections.reverse(res);return res;}
3. 所有点对路径
3.1 思路
对所有顶点进行遍历,创建每一个点的单源路径数组。
3.2 主要代码
public AllPairsPath(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. 路径问题的优化-提前结束递归
4.1 思路
在填充visited和pre数组的时候,如果遇到了目标节点,直接结束。剩下的节点不进行处理。
if(v == t) return true;//程序出口,当到达t顶点时,返回true提前结束递归,而不仅仅是返回return
4.2 主要代码
private boolean dfs(int v, int parent){visited[v] = true;pre[v] = parent;if(v == t) return true; //程序出口,当到达t顶点时,返回true提前结束递归,而不仅仅是返回returnfor(int w: G.adj(v)) //遍历与v相邻的顶点if(!visited[w]) //如果相邻的顶点没有被访问过if(dfs(w, v)) //递归遍历相邻的顶点,如果到达 v==t,则值为truereturn true; //提前返回truereturn false; // 转一圈没法达到t,就可以返回false}
5. 检测环
5.1 思路
从某一点v出发,找到了点w,w被
访问过,并且w不是v的前一个节点
5.2 主要代码
private boolean dfs(int v, int parent){visited[v] = true;for(int w: G.adj(v))if(!visited[w]){ //case1:如果w没有被访问过if(dfs(w, v)) //如果dfs返回true,则说明有环。因为dfs有环才会返回true,那么进入if选择语句return true提前结束return true;}else if(w != parent) // case2:从v出发,找到了w,w还被访问过,并且w不是v的前一个节点return true; // 此时找到了环//其他的情况,找一圈没有找到环,返回falsereturn false;
}
5. 二分图

5.1 思路
二分图可以通过染色过程把顶点区分开,
[-1:顶点还没染色]
[0:一种颜色]
[1:另外一种颜色]
5.2 主要代码
5.2.1 遍历每个联通分量
- dfs(v, 0) 返回true代表相连的两点颜色不一样,暂未出现矛盾;
- dfs(v, 0) 返回false代表相连的两点颜色一样,不符合二分图的定义,因此进入if语句块,设置isBipartite = false;并且提前结束循环。
for(int v = 0; v < G.V(); v ++)if(!visited[v]) //如果没有被访问// 起始的时候把v统一染成0色,如果dfs返回的false,进入下面结构体,否则跳出执行v++if(!dfs(v, 0)){ isBipartite = false; // 检测出错了,就设置成falsebreak; // 后续的循环就不需要进行了}
5.2.2 递归判断相邻两点的颜色是否一致
private boolean dfs(int v, int color){ //参数一:顶点 参数二:颜色visited[v] = true;colors[v] = color;//依次判断相邻顶点w的颜色for(int w: G.adj(v))if(!visited[w]){ //如果w没有被访问过,则进入判断if(!dfs(w, 1 - color)) //如果v的颜色是0,那么w的颜色应该是1。如果v的颜色是1,那么w的颜色应该是0.return false; //如果相邻的两个顶点颜色一样,那么就不是二分图}else if(colors[w] == colors[v]) //如果相邻的两个顶点颜色一样,那么就不是二分图return false;return true;
}
相关文章:
图论03-【无权无向】-图的深度优先遍历-路径问题/检测环/二分图
文章目录 1. 代码仓库2. 单源路径2.1 思路2.2 主要代码 3. 所有点对路径3.1 思路3.2 主要代码 4. 路径问题的优化-提前结束递归4.1 思路4.2 主要代码 5. 检测环5.1 思路5.2 主要代码 5. 二分图5.1 思路5.2 主要代码5.2.1 遍历每个联通分量5.2.2 递归判断相邻两点的颜色是否一致…...
算法题java
一、四向链表,输入n生成一个多维4向链表 Datastatic class ListNode<T>{private T val;ListNode<T> up,down,left,right;public ListNode(T val){this.val val;}}public static void main(String[] args){ListNode<Integer> node getResult(8);…...
MySQL数据的基础语法
MySQL 是一种强大的关系型数据库管理系统(RDBMS),它使用 SQL(Structured Query Language)来管理和操作数据。以下是 MySQL 数据库的基础 SQL 语法,包括创建数据库、创建表、插入、查询、更新和删除数据等基…...
阿里面试(持续更新)
一面: 1 HashMap 实现原理,ConcurrentHashMap 实现原理 HashMap和ConcurrentHashMap都是存储键值对的数据结构,不同的是HashMap是线程不安全的,ConcurrentHashMap是线程安全的,HashMap在高并发情况下会出现数据不一致…...
龙芯3A3000源码编译安装deepin-ide
安装环境 系统为统信专业版1050 CPU为龙芯3A3000 安装步骤 1.安装所有依赖库 sudo apt-get install git debhelper cmake qt5-qmake qtbase5-dev qttools5-dev qttools5-dev-tools lxqt-build-tools libssl-dev llvm llvm-dev libclang-dev libutf8proc-dev libmicrohttpd-d…...
学成在线第二天-查询课程、查询课程分类、新增课程接口实现以及跨域的处理思路和全局异常处理的使用以及面试题
目录 一、接口的实现 二、跨域的处理思路 三、全局异常处理 四、面试题 五、总结 一、接口的实现 1. 查询课程接口 思路: 典型的分页查询 按需查询 模糊查询的查询 controller: ApiOperation(value "课程列表", notes "课程…...
【OpenCV概念】 11— 对象检测
一、说明 这都是关于物体识别的。物体识别是指通过计算机视觉技术,自动识别图像或视频中的物体及其属性和特征,是人工智能领域的一个分支。物体识别可应用于多个领域,包括工业自动化、智能家居、医疗、安防等。请随时阅读这篇文章:…...
TensorRT学习笔记--常用卷积、激活、池化和FC层算子API
目录 1--Tensor算子API 1-1--卷积算子 1-2--激活算子 1-3--池化算子 1-4--FC层算子 2--代码实例 3--编译运行 1--Tensor算子API TensorRT提供了卷积层、激活函数和池化层三种最常用算子的API: // 创建一个空的网络 nvinfer1::INetworkDefinition* network …...
【Edabit 算法 ★☆☆☆☆☆】 Less Than 100?
【Edabit 算法 ★☆☆☆☆☆】 Less Than 100? language_fundamentals math validation Instructions Given two numbers, return true if the sum of both numbers is less than 100. Otherwise return false. Examples lessThan100(22, 15) // true // 22 15 37lessTha…...
C++中的智能指针:更安全、更便利的内存管理
在C++编程中,动态内存管理一直是一个重要且具有挑战性的任务。传统的C++中,程序员需要手动分配和释放内存,这往往会导致内存泄漏和悬挂指针等严重问题。为了解决这些问题,C++11引入了智能指针(Smart Pointers)这一概念,它们是一种高级的内存管理工具,可以自动管理内存的…...
google登录k8s dashboard ui显示“您的连接不是私密连接”问题解决梳理
1.问题描述 OS Version:CentOS Linux release 7.9.2009 (Core) K8S Version:Kubernetes v1.20.4 k8s dashboard ui安装完毕后,通过google浏览器登录返现https网页,发现非官方的https网页无法打开 网址:https://192.168.10.236:31001 2.原…...
MIPS指令集摘要
目录 MIPS指令R I J三种格式 MIPS五种寻址方式 立即数寻址 寄存器寻址 基址寻址 PC相对寻址 伪直接寻址 WinMIPS64汇编指令 助记 从内存中加载数据 lb lbu lh lhu lw lwu ld l.d lui 存储数据到内存 sb sh sw sd s.d 算术运算 daddi daddui dadd…...
数据可视化素材分享 | 数十图表、无数模板
很多人在后台求分享报表、源代码,其实何必这么麻烦,在奥威BI数据可视化平台上点击即可获得大量的可视化素材,如数十种可视化图表,适用于不同分析场景;又如大量不同主题的BI数据可视化报表模板,套用后替换数…...
Hadoop3教程(三十二):(生产调优篇)NameNode故障恢复与集群的安全模式
文章目录 (159)NameNode故障处理(160)集群安全模式&磁盘修复集群安全模式磁盘修复等待安全模式 参考文献 (159)NameNode故障处理 如果NameNode进程挂了并且存储的数据也丢失了,如何恢复Nam…...
uniapp下载附件保存到手机(文件、图片)ios兼容
downloadFile(file),其中file为下载的文件地址uni.downloadFile图片使用uni.saveImageToPhotosAlbum【安卓、ios都合适】文件使用uni.openDocument【安卓图片也可以用这个,ios会失败】 // 下载文件 export function downloadFile(file) {let acceptArr …...
【Edabit 算法 ★☆☆☆☆☆】 Basketball Points
【Edabit 算法 ★☆☆☆☆☆】 Basketball Points language_fundamentals math numbers Instructions You are counting points for a basketball game, given the amount of 2-pointers scored and 3-pointers scored, find the final points for the team and return that …...
Web攻防04_MySQL注入_盲注
文章目录 MYSQL-SQL操作-增删改查盲注概念盲注分类盲注语句参考&更多盲注语句/函数 注入条件-数据回显&错误处理PHP开发项目-注入相关条件:基于延时:基于布尔:基于报错: CMS案例-插入报错&删除延时-PHP&MYSQL1、x…...
Flask自定义装饰和g的使用
1. 在commons.py文件中新增一个装饰器类: 注:一定要加入wraps进行装饰否则,装饰器在给多个函数进行装饰时会报错 from functools import wraps from flask import session, current_app, g# 定义登陆装饰器,封装用户的登陆数据 def user_log…...
【汇编】汇编语言基础知识(学习笔记)
一、汇编语言概述 汇编语言是直接在硬件之上工作的编程语言,首先要了解硬件奈统的结构,才能有效的应用汇编语言对其编程。 二、汇编语言的产生 机器语言:机器语言是机器指令的集合 汇编语言的主体是汇编指令 汇编指令和机器指令的差别在…...
前端 | FormData 用法详解
前端 | FormData 用法详解 介绍 FormData 是 Ajax2.0 对象用以将数据编译成键值对,以便于 XMLHttpRequest 来发送数据。XMLHttpRequest Level 2 提供的一个接口对象,可以使用该对象来模拟和处理表单并方便的进行文件上传操作 如果表单属性设为 mu…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践
01技术背景与业务挑战 某短视频点播企业深耕国内用户市场,但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大,传统架构已较难满足当前企业发展的需求,企业面临着三重挑战: ① 业务:国内用户访问海外服…...
