有向图的强连通分量: Kosaraju算法和Tarjan算法详解
在上一篇文章中, 我们了解了图的最小生成树算法. 本节我们来学习 图的强连通分量(Strongly Connected Component, SCC) 算法.
什么是强连通分量?
在 有向图 中, 若一组节点内的任意两个节点都能通过路径互相到达(例如 A → B A \rightarrow B A→B 且 B → A B \rightarrow A B→A), 则这组节点构成一个强连通分量. 它是图中的最大独立连通单元, 可以看作一种对有向图结构的深层划分.
环境要求
本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.
- Windows: 使用[Visual Studio],
- Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
- GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.
关于 Module 的更多信息, 请参考我之前的博客: CMake 构建 C++20 Module 实例(使用 MSVC)
本项目工程目录: 图论代码
基础概念
在深入算法之前, 我们需要明确几个关键术语和背景知识.
有向图与强连通性
-
强连通性(Strong Connectivity): 若图中任意两节点均能互相到达(即存在 A → B A \rightarrow B A→B , B → A B \rightarrow A B→A的路径), 则该图是强连通的.

上图中任意两点都是强连通的.
-
强连通分量(SCC): 有向图的子集, 其内部节点强连通, 且无法再添加任何其他节点仍保持强连通性(即"最大性").

上图中强连通分量为
{1, 2, 3}
逆图(Transpose Graph)
将原图所有边的方向反转后得到的新图. 例如, 若原图有边 A → B A \rightarrow B A→B, 逆图中则为: B → A B \rightarrow A B→A. 在 Kosaraju 算法中, 逆图帮助定位 SCC 的"边界".

缩点(Condensation)与 DAG
缩点操作是将每个 SCC 合并为一个超级节点, 原图中 SCC 间的边简化为超级节点间的边. 缩点后的图无环路, 这一特性在拓扑排序中至关重要. 通过缩点, 复杂图的分析可简化为对 DAG 的操作(例如路径查找或依赖解析).

3. Kosaraju 算法详解
Kosaraju 算法是计算强连通分量(SCC)的高效算法, 时间复杂度为 O ( V + E ) O(V + E) O(V+E)(线性时间). 其核心思想通过两次深度优先搜索(DFS)实现, 结合逆图(Transpose Graph)和栈(Stack)的特性, 逐层剥离 SCC.
算法步骤
-
第一次 DFS: 标记节点完成顺序
- 对原图进行深度优先搜索, 按节点完成遍历的逆序将节点压入栈(即最后完成的节点在栈顶).
- 关键作用: 确保后续处理时, 从"最晚完成"的节点(即潜在 SCC 的"根")开始, 保证 SCC 的完整性.
-
构建逆图
- 将原图所有边的方向反转, 生成逆图(Transpose Graph).
-
第二次 DFS: 提取 SCC
- 按栈中节点的顺序, 依次从栈顶取出节点, 对逆图进行 DFS.
- 每轮 DFS 访问的节点构成一个 SCC.
原理剖析
-
为何需要逆图?
SCC 的强连通性在逆图中保持不变, 但逆图的遍历顺序能天然隔离不同 SCC 的边界.- 例如, 原图中存在
A→B, 逆图中则为B→A. 若A和B属于同一 SCC, 逆图的 DFS 仍能覆盖两者; 若属于不同 SCC, 逆图的遍历顺序会避免跨分量污染.
- 例如, 原图中存在
-
栈的作用
第一次 DFS 的逆序栈隐含了原图的拓扑排序(忽略环路), 确保第二次 DFS 从"高层级"分量开始, 避免重复遍历.
伪代码实现
Kosaraju(G):// G 是一个有向图// Step 1: 对原图G执行深度优先搜索,并记录每个节点的完成时间finish_time = [] // 这里我们用一个列表存储按完成时间排序的节点visited = [false] * |V| // 初始化所有节点为未访问状态for each vertex u in G:if not visited[u]:DFS(G, u, visited, finish_time)// Step 2: 转置图G,得到G^TGT = transpose(G)// 重置访问标记数组visited = [false] * |V|// Step 3: 对转置后的图GT执行深度优先搜索,按照原图的完成时间顺序while finish_time is not empty:v = finish_time.pop() // 取出最后一个元素,即具有最大完成时间的节点if not visited[v]:// 打印或处理这个强连通分量print("SCC:")DFS(GT, v, visited) // 注意这里不需要更新finish_time// 深度优先搜索辅助函数
DFS(graph, start_vertex, visited, finish_time=None):visited[start_vertex] = truefor each neighbor in graph.adjacent(start_vertex):if not visited[neighbor]:DFS(graph, neighbor, visited, finish_time)if finish_time is not None:finish_time.append(start_vertex) // 在递归返回时记录节点
示例演示
假设原图如下(边为有向):

-
第一次 DFS: 假设遍历顺序为
A -> B -> C -> D -> E -> F, 栈中顺序为栈底[F, E, D, C, B, A]栈顶.
-
构建逆图: 所有边反转.

-
第二次 DFS: 依次弹出栈顶元素处理, 并 DFS 逆图:
-
从
A出发, DFS 访问A -> C -> B, 组成 SCC{A, B, C}.
-
相关文章:
有向图的强连通分量: Kosaraju算法和Tarjan算法详解
在上一篇文章中, 我们了解了图的最小生成树算法. 本节我们来学习 图的强连通分量(Strongly Connected Component, SCC) 算法. 什么是强连通分量? 在 有向图 中, 若一组节点内的任意两个节点都能通过路径互相到达(例如 A → B A \rightarrow B A→B 且 B → A B \rightarro…...
mac相关命令
显示和隐藏usr等隐藏文件文件 terminal输入: defaults write com.apple.Finder AppleShowAllFiles YESdefaults write com.apple.Finder AppleShowAllFiles NO让.bashrc每次启动shell自动生效 编辑vim ~/.bash_profile 文件, 加上 if [ -f ~/.bashrc ]; then. ~/.bashrc fi注…...
代码随想录算法训练营第六天| 242.有效的字母异位词 、349. 两个数组的交集、202. 快乐数 、1. 两数之和
242.有效的字母异位词 题目链接:242.有效的字母异位词 文档讲解:代码随想录有效的字母异位词 视频讲解:LeetCode:有效的字母异位词 状态:学会了 思路: 数组其实是简单哈希表。 哈希表用来快速判断元素是否在…...
dify实现分析-rag-关键词索引的实现
概述 在dify中有两种构建索引的方式,一种是经济型,另一种是高质量索引(通过向量数据库来实现)。其中经济型就是关键词索引,通过构建关键词索引来定位查询的文本块,而关键词索引的构建是通过Jieba这个库来完…...
【小白学HTML5】一文讲清常用单位(px、em、rem、%、vw、vh)
html5中,常用的单位有px、em、rem、%、vw、vh(不常用)、cm、m等,这里主要讲解px、em、rem、%、vw。 学习了解:主流浏览器默认的字号:font-size:16px,无论用什么单位,浏览器最终计算…...
Fastgpt学习(5)- FastGPT 私有化部署问题解决
1.☺ 问题描述: Windows系统,本地私有化部署,postgresql数据库镜像日志持续报错" data directory “/var/lib/postgresql/data” has invalid permissions ",“ DETAIL: Permissions should be urwx (0700) or urwx,gr…...
ubuntu下安装TFTP服务器
在 Ubuntu 系统下安装和配置 TFTP(Trivial File Transfer Protocol)服务器可以按照以下步骤进行: 1. 安装 TFTP 服务器软件包 TFTP 服务器通常使用 tftpd-hpa 软件包,你可以使用以下命令进行安装: sudo apt update …...
深入解析 iText 7:从 PDF 文档中提取文本和图像
在现代开发中,PDF 文件的操作是不可避免的一部分。无论是生成报告、解析文档,还是从文件中提取信息,我们常常需要处理 PDF 文件。iText 是一个非常强大的库,广泛应用于 PDF 文件的创建、修改和解析。自 iText 7 发布以来ÿ…...
Rust编程语言入门教程 (六)变量与可变性
Rust 系列 🎀Rust编程语言入门教程(一)安装Rust🚪 🎀Rust编程语言入门教程(二)hello_world🚪 🎀Rust编程语言入门教程(三) Hello Cargo…...
事务--实操演示
目录 一、准备工作 二、在MySQL中操作事务(重点) 第一种方式:使用命令的方式 第二种方式:设置MySQL事务不默认提交的方式 结 三、在JDBC中操作事务(掌握) 第一种方式:使用命令的方式 第…...
PHP是如何并行异步处理HTTP请求的?
文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons:JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram,自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 ? 5 IDEA必装的插件&…...
【Spring详解一】Spring整体架构和环境搭建
一、Spring整体架构和环境搭建 1.1 Spring的整体架构 Spring框架是一个分层架构,包含一系列功能要素,被分为大约20个模块 Spring核心容器:包含Core、Bean、Context、Expression Language模块 Core :其他组件的基本核心ÿ…...
在 Vue 3 中使用 Lottie 动画:实现一个加载动画
在现代前端开发中,动画是提升用户体验的重要元素之一。Lottie 是一个流行的动画库,它允许我们使用 JSON 文件来渲染高质量的动画。本文将介绍如何在 Vue 3 项目中集成 Lottie 动画,并实现一个加载动画效果。 如果对你有帮助请帮忙点个&#x…...
深度解析:使用 Headless 模式 ChromeDriver 进行无界面浏览器操作
一、问题背景(传统爬虫的痛点) 数据采集是现代网络爬虫技术的核心任务之一。然而,传统爬虫面临多重挑战,主要包括: 反爬机制:许多网站通过检测请求头、IP地址、Cookie等信息识别爬虫,进而限制…...
MySQL 主从复制原理及其工作过程
一、MySQL主从复制原理 MySQL 主从复制是一种将数据从一个 MySQL 数据库服务器(主服务器,Master)复制到一个或多个 MySQL 数据库服务器(从服务器,Slave)的技术。以下简述其原理,主要包含三个核…...
计算机网络抄手 运输层
一、运输层协议概述 1. 进程之间的通信 从通信和信息处理的角度看,运输层向它上面的应用层提供通信服务,它属于面向通信部分的最高层,同时也是用户功能中的最低层。当网络边缘部分的两台主机使用网络核心部分的功能进行端到端的通信时&…...
字符串函数和结构题内存对齐
图下为函数使用: #include <ctype.h>int main() {int ret isdigit(Q);printf("%d\n", ret);return 0; }int main() {printf("%c\n", toupper(a));printf("%c\n", tolower(A));return 0; }...
【嵌入式Linux应用开发基础】特殊进程
目录 一、守护进程(Daemon Process) 1.1. 概念 1.2. 特点 1.3. 守护进程的命名 1.4. 创建守护进程的步骤 1.5. 守护进程的实例 1.6. 守护进程的管理 1.7. 影响与处理 二、僵尸进程(Zombie Process) 2.1. 僵尸进程的定义…...
深度学习pytorch之19种优化算法(optimizer)解析
提示:有谬误请指正 摘要 本博客详细介绍了多种常见的深度学习优化算法,包括经典的LBFGS 、Rprop 、Adagrad、RMSprop 、Adadelta 、ASGD 、Adamax、Adam、AdamW、NAdam、RAdam以及SparseAdam等,通过对这些算法的公式和参数说明进行详细解析…...
rust笔记5-derive属性2
在 Rust 中,derive 是一种自动为结构体或枚举实现特定 trait 的机制。通过 #[derive(...)] 属性,Rust 编译器可以自动生成一些常见 trait 的实现代码,从而减少手动编写重复代码的工作量。 以下是对 Copy、Clone、Hash 和 Default 这几个常用 trait 的详细介绍和示例: 1. C…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
基于Flask实现的医疗保险欺诈识别监测模型
基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施,由雇主和个人按一定比例缴纳保险费,建立社会医疗保险基金,支付雇员医疗费用的一种医疗保险制度, 它是促进社会文明和进步的…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀”
深入浅出JavaScript中的ArrayBuffer:二进制数据的“瑞士军刀” 在JavaScript中,我们经常需要处理文本、数组、对象等数据类型。但当我们需要处理文件上传、图像处理、网络通信等场景时,单纯依赖字符串或数组就显得力不从心了。这时ÿ…...
中科院1区顶刊|IF14+:多组学MR联合单细胞时空分析,锁定心血管代谢疾病的免疫治疗新靶点
中科院1区顶刊|IF14:多组学MR联合单细胞时空分析,锁定心血管代谢疾病的免疫治疗新靶点 当下,免疫与代谢性疾病的关联研究已成为生命科学领域的前沿热点。随着研究的深入,我们愈发清晰地认识到免疫系统与代谢系统之间存在着极为复…...
