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

python 实现Tarjan 用于在有向图中查找强连通分量的算法

Tarjan 用于在有向图中查找强连通分量的算法介绍

Tarjan算法是一种用于在有向图中查找强连通分量的高效算法,由Robert Tarjan在1972年提出。强连通分量是指在有向图中,如果从顶点u到顶点v以及从顶点v到顶点u都存在一条路径,那么顶点u和顶点v是强连通的。这些顶点组成的集合被称为强连通分量(Strongly Connected Component,简称SCC)。

Tarjan算法的核心思想是通过深度优先搜索(DFS)遍历图,并使用堆栈来追踪搜索过程中的顶点。在遍历的过程中,对每个顶点进行标记,记录其在搜索树中的深度和最小后向边的深度。如果发现某个顶点的后继节点指向了一个已经被访问过的顶点,并且这个顶点在当前的DFS搜索树中(即它还在栈中),那么这个顶点及其所有后继节点(在栈中且未被处理为其他强连通分量的部分)构成一个强连通分量。

Tarjan算法中最重要的两个数组是low[maxn]和dfn[maxn]:

low[u]代表u可以到达的深度最低的节点的深度值,即u能追溯到的最早被访问到的节点的时间戳。
dfn[u]代表u在DFS树中的深度,即u被访问时的时间戳。

算法的基本步骤如下:

初始化所有顶点的dfn和low值为未定义(通常可以设为无穷大或特定标记)。
对每个未访问的顶点v,进行DFS遍历。
将v标记为已访问,并将其dfn[v]和low[v]设置为当前时间戳。
将v压入栈中。
遍历v的所有邻接点w。
如果w未访问过,则递归地对w进行DFS,并在返回后更新low[v]为min(low[v], low[w])。
如果w已访问过且在栈中(即w是v的后继节点且尚未被处理为其他强连通分量的部分),则更新low[v]为min(low[v], dfn[w])。
如果dfn[v] == low[v],则栈中从v到栈顶的所有顶点构成一个强连通分量,将它们弹出栈并标记为同一个强连通分量。

Tarjan算法的时间复杂度为O(V + E),其中V表示图中的顶点数,E表示图中的边数。由于只需要一次DFS遍历即可找到所有的强连通分量,因此Tarjan算法是一种高效的强连通分量查找算法。

以上是对Tarjan算法用于在有向图中查找强连通分量的简要介绍。如需更详细的信息或示例代码,请参考相关算法书籍或在线资源。

Tarjan 用于在有向图中查找强连通分量的算法python实现样例

以下是Python中实现Tarjan算法查找强连通分量的示例代码:

class Tarjan:def __init__(self, graph):self.graph = graphself.num_nodes = len(graph)self.index = 0self.lowlink = [0] * self.num_nodesself.on_stack = [False] * self.num_nodesself.stack = []self.scc = []def tarjan_scc(self):for i in range(self.num_nodes):if self.lowlink[i] == 0:self.strong_connect(i)return self.sccdef strong_connect(self, v):self.index += 1self.lowlink[v] = self.indexself.stack.append(v)self.on_stack[v] = Truefor w in self.graph[v]:if self.lowlink[w] == 0:self.strong_connect(w)self.lowlink[v] = min(self.lowlink[v], self.lowlink[w])elif self.on_stack[w]:self.lowlink[v] = min(self.lowlink[v], self.lowlink[w])if self.lowlink[v] == self.index:scc_component = []while True:w = self.stack.pop()self.on_stack[w] = Falsescc_component.append(w)if w == v:breakself.scc.append(scc_component)

使用示例:

# 创建有向图的邻接表表示
graph = [[1],[2],[0, 3],[4],[5],[3]
]# 创建Tarjan对象
tarjan = Tarjan(graph)# 调用tarjan_scc方法查找强连通分量
scc = tarjan.tarjan_scc()# 输出强连通分量
for component in scc:print(component)

输出结果:

[0, 1, 2]
[3]
[4, 5]

以上代码实现了Tarjan算法用于在有向图中查找强连通分量。算法首先初始化相关数据结构,包括索引、低链接、栈等。然后按照Tarjan算法的步骤进行深度优先搜索,并在搜索过程中记录每个节点的索引和低链接值。当找到一个强连通分量时,从栈中弹出节点,直到找到当前节点为止,并将这些节点组成一个强连通分量。最终,算法返回所有的强连通分量。

相关文章:

python 实现Tarjan 用于在有向图中查找强连通分量的算法

Tarjan 用于在有向图中查找强连通分量的算法介绍 Tarjan算法是一种用于在有向图中查找强连通分量的高效算法,由Robert Tarjan在1972年提出。强连通分量是指在有向图中,如果从顶点u到顶点v以及从顶点v到顶点u都存在一条路径,那么顶点u和顶点v…...

Qt开发技巧(十五)字符串去除空格,跨网段搜索不生效,设置图片显示失败问题,表格视图的批量删除,主动判断字串编码,开启向前查询的属性,画家类载入html来绘制

继续讲一些Qt开发中的技巧操作: 1.字符串去除空格 我们经常会遇到字符串重去除空格的情况,对于QString去除空格,有多种场景,可能需要去除左侧、右侧、所有等位置的空格; //字符串去空格 -1移除左侧空格 0移除所有空格…...

【机器学习】智驭未来:探索机器学习在食品生产中的革新之路

📝个人主页🌹:Eternity._ 🌹🌹期待您的关注 🌹🌹 ❀目录 🔍1. 引言:探索机器学习在食品生产中的革新之路📒2. 机器学习在食品质量控制中的应用🌞实…...

Ubuntu 安装CUDA并使用Docker配置Pytorch环境

文章目录 参考安装顺序Nvidia GPU driverDockerNvidia Container ToolkitDocker PyTorch 1. Nvidia GPU Driver2. Docker 安装(使用apt存储库进行安装)3. Nvidia Container Toolkit3.1 Docker测试GPU 参考 安装顺序 Nvidia GPU driver Docker Nvidia…...

【论文阅读】Simulating 500 million years of evolution with a language model

Simulating 500 million years of evolution with a language model 1、概述 展示了语言模型在蛋白质设计和进化模拟方面的能力。通过对 ESM3 模型的研究,发现其能够生成与自然蛋白质差异较大且具有功能的新蛋白质,如新型绿色荧光蛋白(GFP),表明语言模型可以达到自然进化…...

detectron2/layers源码笔记

from .wrappers import ( BatchNorm2d, Conv2d, #在torch.conv2d的基础上集成了norm层和activation层 ConvTranspose2d, cat, interpolate, Linear, nonzero_tuple, #nonzero_tuple(x)得到tuple of 每个维度的索引 cross_entropy, empty_input_loss_func…...

LLM+知识图谱新工具! iText2KG:使用大型语言模型构建增量知识图谱

iText2KG是一个基于大型语言模型的增量知识图谱构建工具,通过从文本文档中提取实体和关系来逐步构建知识图谱。该工具具有零样本学习能力,能够在无需特定训练的情况下,在多个领域中进行知识提取。它包括文档提炼、实体提取和关系提取模块&…...

React基础-快速梳理

React介绍 React由Meta公司开发,是一个用于构建Web和原生交互界面的库 React的优势 相较于传统基于DOM开发的优势 组件化的开发方式不错的性能 相较于其它前端框架的优势 丰富的生态跨平台支持 开发环境创建 create-react-app是一个快速创建React开发环境的…...

H.264编解码 - NALU详解

一、概述 NALU(Network Abstraction Layer Unit)是H.264编解码中的一个重要概念。H.264是一种视频压缩标准,将视频数据分割成一系列的NALU。每个NALU都是一个独立的数据单元,包含视频压缩后的一个片段。每个NALU都有自己的起始码和长度前缀,用于标识NALU的起始位置和长度。…...

vSAN02:容错、存储策略、文件服务、快照与备份、iSCSI

目录 vSAN容错条带化存储策略1. 创建新策略2. 应用存储策略 vSAN文件服务文件服务快照与备份 vSAN iSCSI目标服务 vSAN容错 FTT:Fault to Tolerance 允许故障数 故障域:每一台vSAN主机是一个故障域 - 假设3台超融合(3计算1存储)&…...

图解C#高级教程(四):协变、逆变

本章的主题是可变性(variance),这里的可变性更多的是指基类和派生类之间的转换。可变性分为三种:协变(covariance)、逆变(contravariance)和不变(invariance)…...

详解CSS中的伪元素

4.3 伪元素 可以把样式应用到文档树中根本不存在的元素上。 ::first-line 文本中的第一行 ::first-letter 文本中的第一个字母 ::after 元素之后添加 ::before 元素之前 代码&#xff1a; <!DOCTYPE html> <html> <head><meta charset"utf-8&q…...

paper_template

paper_template Title 文章标题 Abstract 摘要 Keywords 关键词 Highlights Highlights / 创新点 Summary 写完笔记之后最后填&#xff0c;概述文章的内容&#xff0c;以后查阅笔记的时候先看这一段。 Backgrounds 描述当前研究背景 Research Objective 作者的研…...

【Bug】解决 Ubuntu 中 “error: Unable to Find Python3 Executable” 错误

解决 Ubuntu 中 “Unable to Find Python3 Executable” 错误 在 Ubuntu 系统上使用 Python 进行开发时&#xff0c;遇到找不到 python3 可执行文件的错误。 主要问题是无法正常打开终端&#xff08;原生与terminator&#xff09;&#xff0c;找不到python3&#xff0c;且无法…...

CUDA与TensorRT学习六:模型部署-CNN、模型部署-YOLOv8检测器、部署BEVFusion模型

文章目录 一、模型部署-CNN二、模型部署-YOLOv8检测器三、部署BEVFusion模型 一、模型部署-CNN 二、模型部署-YOLOv8检测器 三、部署BEVFusion模型...

防sql注入的网站登录系统设计与实现

课程名称 网络安全 大作业名称 防sql注入的网站登录系统设计与实现 姓名 学号 班级 大 作 业 要 求 结合mysql数据库设计一个web登录页面密码需密文存放&#xff08;可以采用hash方式&#xff0c;建议用sha1或md5加盐&#xff09;采用服务器端的验证码&#…...

如何快速切换电脑的ip地址

在当今的数字化时代&#xff0c;IP地址作为网络身份的重要标识&#xff0c;其重要性日益凸显。无论是出于保护个人隐私的需要&#xff0c;还是为了访问特定的网络服务等&#xff0c;快速切换电脑的IP地址已成为许多用户的迫切需求。本文将为你介绍几种实用的方法&#xff0c;帮…...

鸿蒙HarmonyOS之选择相册文件(照片/视频)方法

一、新建文件工具类FileUtil.ets 包含&#xff1a;选择照片方法、获取文件类型方法、去除后缀、获取后缀方法 import { BusinessError, request } from kit.BasicServicesKit; import photoAccessHelper from ohos.file.photoAccessHelper; import bundleManager from ohos.b…...

【QT Qucik】C++交互:接收QML信号

在本节课中&#xff0c;我们将深入探讨如何在C中接收QML发出的信号。我们将分为几个部分&#xff0c;详细说明信号的定义、发送及其在C中的接收。 理解信号和槽机制 Qt的信号与槽机制是一种用于对象之间通信的强大工具。信号是对象在特定事件发生时发送的通知&#xff0c;而槽…...

【C++】关键字+命名空间

大家好&#xff0c;我是苏貝&#xff0c;本篇博客带大家了解C的命名空间&#xff0c;如果你觉得我写的还不错的话&#xff0c;可以给我一个赞&#x1f44d;吗&#xff0c;感谢❤️ 目录 一. 关键字二. 命名空间2.1 命名空间的定义2.2 命名空间的使用a. 命名空间名称作用域限定…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

vue3 daterange正则踩坑

<el-form-item label"空置时间" prop"vacantTime"> <el-date-picker v-model"form.vacantTime" type"daterange" start-placeholder"开始日期" end-placeholder"结束日期" clearable :editable"fal…...