首页 > 编程语言 >Kosaraju 算法

Kosaraju 算法

时间:2024-05-03 22:15:40浏览次数:22  
标签:tarjan 复杂度 算法 DFS Kosaraju 反图

引入

Kosaraju 算法用于求解强连通分量,在稠密图下复杂度会比 tarjan 算法要优秀。(?

过程

  1. 对整个图进行搜索,并且将没一个顶点按照 DFS 序压入栈中。

  2. 建一个反图。

  3. 对于栈中的每一个点再反图上跑一遍 DFS,现在跑出来的子图即为一个强连通分量。

  4. 标记这几个点。

  5. 重复执行操作3,4,直到栈为空。

code

复杂度

其最坏情况就是每个点和每一条边都需要进行两次 DFS,这样子的复杂度为 \(O(N + E)\)。\(N\) 为点数,\(E\) 为边数。但是一般都是跑不满的。

在稠密图上表现良好,个人认为这个算法会比 tarjan 好写许多。

标签:tarjan,复杂度,算法,DFS,Kosaraju,反图
From: https://www.cnblogs.com/Carousel/p/18171709

相关文章

  • m基于LDPC编译码的matlab误码率仿真,对比SP,MS,NMS以及OMS四种译码算法
    1.算法仿真效果matlab2022a仿真结果如下:    2.算法涉及理论知识概要       低密度奇偶校验码(LDPC)译码是现代通信系统中一种高效的错误校正技术,广泛应用于无线通信、卫星通信和数据存储等领域。LDPC码因其良好的纠错性能和接近香农极限的潜力而受到重视。本文......
  • 算法基础课笔记
    二分整数二分有单调性一定可以二分,二分不一定有单调性数的范围intmain(){scanf("%d%d",&n,&m);for(inti=0;i<n;i++)scanf("%d",&q[i]);while(m--){intx;scanf("%d",&x);intl......
  • 代码随想录算法训练营第10天 | 栈和队列 232.用栈实现队列 225.用队列实现栈
    leetcode232.用栈实现队列题目232.用栈实现队列请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):实现MyQueue类:voidpush(intx)将元素x推到队列的末尾intpop()从队列的开头移除并返回元素intpeek()返回队列开头的......
  • raft算法和etcd代码解析-5.应用模块的启动
    Node接口Node是raft应用模块在节点上的抽象,也是应用模块和算法模块交互的入口应用模块持有Node作为算法模块的引用,通过调用Node接口的API与算法模块通信,通信方式是通过若干个Channel异步完成的。//Noderepresentsanodeinaraftcluster.typeNodeinterface{ //告知......
  • 读天才与算法:人脑与AI的数学思维笔记16_音乐图灵测试
    1.      艾米1.1.        人工智能作曲家1.1.1.          分析机可能会生成任意复杂程度、精细程度的科学的音乐作品1.1.1.1.           阿达·洛夫莱斯1.1.2.          巴赫的作品是大多数作曲家开始学习创作的起点,也是......
  • 随机森林Adaboosting算法与Python实现(二)
    AdaBoost是Freund和Schapire于1996年提出的一种集成学习方法。它的核心思想是通过迭代训练一系列弱分类器,每次调整样本权重以便更好地拟合被前一轮分类器错误分类的样本,从而构建一个强分类器。最终的模型是基于这些弱分类器的加权组合。AdaBoost广泛应用于二分类和多分类问题,尤其......
  • leetcode算法热题--最长连续序列
    题目给定一个未排序的整数数组nums,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。请你设计并实现时间复杂度为O(n)的算法解决此问题。示例1:输入:nums=[100,4,200,1,3,2]输出:4解释:最长数字连续序列是[1,2,3,4]。它的长度为4。示例2:输入:nums=......
  • 基于有限体积法和交错网格的SIMPLE算法推导及实现
    基于有限体积法和交错网格的SIMPLE算法推导及实现SIMPLE算法,半隐式速度压力耦合算法,是专门求解不可压流体流动的算法。由于不可压流体控制方程中,密度常常被视为常数,没有表征流体密度、压力、温度联系的状态方程,压力以梯度项的形式存在于动量方程中,无法显性表达或者直接求解,造成了......
  • 个人的一种设想:能否使用元强化学*算法解决路径导航问题 —— 快速的适配于相似结构的
    pathfinding是人工智能领域的一个老问题,随着humanoid的应用火热起来这个问题也随之再度受关注。比较传统的人工智能方法一般都是使用A*这样的启发式的算法,不仅在2D领域同时也在3D(Voxelspace)领域有着较好的表现,不过随着深度学*和强化学*的*些年的快速发展也就有了一些使用深度强......
  • 数论学习笔记 (4):扩展欧几里得算法
    概述扩展欧几里得算法(\(exgcd\))可以用来求形如\(ax+by=c\)的不定方程的通解。铺垫-\(\small\texttt{ax+by=gcd(a,b)}\)的解\(exgcd\)的思想是在用辗转相除法递归\(gcd(a,b)\)的回溯时求出对应方程\(ax+by=gcd(a,b)\)的解。考虑方程\(ax+by=gcd(a,b)\)。看回辗......