深度优先遍历与连通分量
深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时,则回到上一个顶点,继续试探别的顶点,直至所有的顶点都被访问过。
下图示例的图从 0 开始遍历顺序如右图所示:

无向图 G 的一个极大连通子图称为 G 的一个连通分量(或连通分支)。连通图只有一个连通分量,即其自身;非连通的无向图有多个连通分量。连通分量与连通分量之间没有任何边相连。深度优先遍历可以用来求连通分量。
下面以求连通分量为例,来实现图的深度优先遍历,称为 dfs。下面代码片段中,visited 数组记录 dfs 的过程中节点是否被访问,ccount 记录联通分量个数,id 数组代表每个节点所对应的联通分量标记,两个节点拥有相同的 id 值代表属于同一联通分量。
...
// 构造函数, 求出无权图的联通分量
public Components(Graph graph){// 算法初始化G = graph;visited = new boolean[G.V()];id = new int[G.V()];ccount = 0;for( int i = 0 ; i < G.V() ; i ++ ){visited[i] = false;id[i] = -1;}// 求图的联通分量for( int i = 0 ; i < G.V() ; i ++ )if( !visited[i] ){dfs(i);ccount ++;}
}
...
图的深度优先遍历是个递归过程,实现代码:
...
// 图的深度优先遍历
void dfs( int v ){visited[v] = true;id[v] = ccount;for( int i: G.adj(v) ){if( !visited[i] )dfs(i);}
}
...
Java 实例代码
src/runoob/graph/Components.java 文件代码:
package runoob.graph;import runoob.graph.read.Graph;/*** 深度优先遍历*/
public class Components {Graph G; // 图的引用private boolean[] visited; // 记录dfs的过程中节点是否被访问private int ccount; // 记录联通分量个数private int[] id; // 每个节点所对应的联通分量标记// 图的深度优先遍历void dfs( int v ){visited[v] = true;id[v] = ccount;for( int i: G.adj(v) ){if( !visited[i] )dfs(i);}}// 构造函数, 求出无权图的联通分量public Components(Graph graph){// 算法初始化G = graph;visited = new boolean[G.V()];id = new int[G.V()];ccount = 0;for( int i = 0 ; i < G.V() ; i ++ ){visited[i] = false;id[i] = -1;}// 求图的联通分量for( int i = 0 ; i < G.V() ; i ++ )if( !visited[i] ){dfs(i);ccount ++;}}// 返回图的联通分量个数int count(){return ccount;}// 查询点v和点w是否联通boolean isConnected( int v , int w ){assert v >= 0 && v < G.V();assert w >= 0 && w < G.V();return id[v] == id[w];}
}相关文章:
深度优先遍历与连通分量
深度优先遍历(Depth First Search)的主要思想是首先以一个未被访问过的顶点作为起始顶点,沿当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时,则回到上一个顶点,继续试探别的顶点,直至所有的顶点都被访问过。 下图示例的…...
Python学习笔记--类的继承
七、类的继承 1、定义类的继承 说到继承,你一定会联想到继承你老爸的家产之类的。 类的继承也是一样。 比如有一个旧类,是可以算平均数的。然后这时候有一个新类,也要用到算平均数,那么这时候我们就可以使用继承的方式。新类继…...
全自动批量AI改写文章发布软件【软件脚本+技术教程】
项目原理: 利用AI工具将爆款文章改写发布到平台上流量变现,通过播放量赚取收益 软件功能: 1.可以根据你选的文章领域,识别你在网站上抓取的文章链接进来自动洗稿生成过原创的文章,自动配图 2.同时还可以将管理的账号导入进脚本软…...
strongswan:configure: error: OpenSSL Crypto library not found
引子 在配置strongswan时,有时会遇到以下错误(其实所有需要openssl的软件configure时都有可能遇到该问题): configure: error: OpenSSL Crypto library not found 解决方法 crypto是什么呢? 是OpenSSL 加密库(lib), 这个库需要op…...
Xcode 常见错误
1. Xcode 15 编译出现以下错误 clang: error: SDK does not contain libarclite at the path /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/lib/arc/libarclite_iphonesimulator.a; try increasing the minimum deployment target 从…...
【JavaEE】实现简单博客系统-前端部分
文件目录: 展示: blog_list.html: <!DOCTYPE html> <html lang"cn"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><t…...
首发scitb包,一个为制作统计表格而生的R包
目前,本人写的第3个R包scitb包已经正式在R语言官方CRAN上线,scitb包是一个为生成专业化统计表格而生的R包。 可以使用以下代码安装 install.packages("scitb")scitb包对我而言是个很重要的R包,我的很多想法需要靠它做平台来实现&a…...
2023-11-06 LeetCode每日一题(最大单词长度乘积)
2023-11-06每日一题 一、题目编号 318. 最大单词长度乘积二、题目链接 点击跳转到题目位置 三、题目描述 给你一个字符串数组 words ,找出并返回 length(words[i]) * length(words[j]) 的最大值,并且这两个单词不含有公共字母。如果不存在这样的两个…...
numpy机器学习深度学习 常用函数
Python numpy(np)创建空的字符串数组、矩阵。解决数组中每个元素仅保留单个字符,无法完整填入字符串。 matrix1np.zeros(shape(31,22)).astype(np.str_) matrix1[matrix1 0.0] 1.reshape()方法 作用是将数据按照指定的维度重新组织并返回。也就是reshape&#x…...
连接器切断机维修
目录 起因 机器出现的问题排查 问题 检查 维修方法 今天也开始了设备的维修记录,今天出问题的是连接器切断器的维护! 起因 “连接器切断机坏了,有没有维修的,机器不动了,没有报警,没有断电和气管的泄漏&…...
Mysql数据库 8.SQL语言 外键约束
一、外键约束 外键约束——将一个列添加外键约束与另一张表的主键(唯一列)进行关联之后,这个外键约束的列添加的数据必须要在关联的主键字段中存在 案例 创建原则:先创建不含外键的表也就是班级表 添加外键的方式 一般使用第一…...
ERROR in static/js/xxx.js from UglifyJs Unexpected token name «currentVersion»
添加链接描述 ERROR in static/js/xxx.js from UglifyJs Unexpected token name currentVersion, expected punc 遇到这种异常, 需要运行下面脚本运行npm i -D uglifyjs-webpack-pluginbeta修改webpack.prod.conf.jsjs中引入参数const UglifyJsPlugin require(uglifyjs-webpa…...
反序列化 [网鼎杯 2020 青龙组]AreUSerialz 1
打开题目 <?phpinclude("flag.php");highlight_file(__FILE__);class FileHandler {protected $op;protected $filename;protected $content;function __construct() {$op "1";$filename "/tmp/tmpfile";$content "Hello World!&qu…...
JWT登录校验
工作原理 下面来详细看看 UTF-8 是如何工作的,以及为什么它会根据被编码的字符具有不同的长度。 一、JWT是什么? 在介绍JWT之前,我们先来回顾一下利用token进行用户身份验证的流程: 1、客户端使用用户名和密码请求登录 2、服务端…...
python发送企业微信群webhook消息(文本、文件)
import datetime import os import time from copy import copyimport requests from loguru import logger from urllib3 import encode_multipart_formdataclass WeiXin_Robot:def __init__(self,url: str ""):# 测试cartest_url "https://qyapi.weixin.qq.…...
高数笔记06:无穷级数
图源:文心一言 时间比较紧张,仅导图~~🥝🥝 第1版:查资料、画导图~🧩🧩 参考资料:《高等数学 基础篇》武忠祥 🐳目录 🐳常数项级数 🐋概要 &…...
Android工具栏ToolBar
主流APP除了底部有一排标签栏外,通常顶部还有一排导航栏。在Android5.0之前,这个顶部导航栏以ActionBar控件的形式出现,但AcionBar存在不灵活、难以扩展等毛病,所以Android5.0之后推出了ToolBar工具栏控件,意在取代Aci…...
2.3 - 网络协议 - ICMP协议工作原理,报文格式,抓包实战
「作者主页」:士别三日wyx 「作者简介」:CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」:对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 ICMP协议 1、ICMP协议工作原理2、ICMP协议报文格式…...
北京陪诊小程序|陪诊系统开发|陪诊小程序未来发展不可小觑
近几年随着互联网快速发展,各行业领域都比较注重线上服务系统,通过陪诊小程序开发可以满足更多用户使用需求,同时还能提高用户使用体验。现在陪诊类的软件应用得到全面推广,在医疗行业当中陪诊小程序更贴近用户生活,可…...
前端面试题总结(一)
1. vue性能优化 v-if和v-show使用:频繁切换使用v-show(display样式),反之使用v-if(删除与新值DOM)v-for必须加key,不能使用index当作key(使用index,如果数组发生变化&am…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂
蛋白质结合剂(如抗体、抑制肽)在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上,高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术,但这类方法普遍面临资源消耗巨大、研发周期冗长…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...
