百科问答小站 logo
百科问答小站 font logo



算法导论求有向图强连通分量:按拓扑排序,求反向图的DFS。若改成按拓扑排序倒序,用原图做DFS,错在哪? 第1页

  

user avatar   feng-kuang-shen-shi-92 网友的相关建议: 
      

原图不行,能求出的是一个环但不是回路。求回路有3个经典算法。

1、ISM/AISM

在讲求强连通子集的时候,先了解一个文科生常用的方法,解释结构模型与对抗解释结构模型。

上面一篇是一个艺术设计的,然后发了一篇在计算机刊物中的论文。里面用到了AISM可以去看看。

上面是AISM的一个计算地址,它的第一步就是求强连通分量。

2、求强连通分量的三大算法

kosaraju(克鲁斯克尔)算法是用于求有向图的强连通分量的算法之一

时间复杂度:O(M+N) 注:M代表边数,N代表顶点数。

这个就是题主说的。

Tarjan算法是用于求有向图的强连通分量

Tarjan算法的用途之一是,求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大强连通分量。

时间复杂度:O(M+N) 注:M代表边数,N代表顶点数。

Gabow算法是用于求有向图的强连通分量

Gabow算法的用途之一是,求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大强连通分量。

这个其实就是双指针。

上面三个方法其实是一回事。

上面是三种方法的速度比较。




  

相关话题

  对 n × n 网格图,从左下角走到右上角的边不重复路径(即左下角到右上角的迹)有多少种? 
  这张图中能数出多少个三角形? 
  哪段代码最能代表程序员的暴力美学? 
  Metropolis 蒙特卡罗方法、动力学蒙特卡罗方法、分子动力学方法这三种模拟方法有何特点与差异? 
  智能座舱的算法包括哪些方面? 
  哪些开发会用到微积分、离散数学、线性代数、概率论的知识? 
  Network Topology网络拓扑有没有好的专业教材? 
  如何评价b站up主图灵的猫关于tiktok的视频? 
  如何通俗地讲解 viterbi 算法? 
  算法研究属于数学专业还是计算机专业? 

前一个讨论
一个关于拓扑排序的扩展问题,可以做到的最优复杂度是?
下一个讨论
请教拓扑排序中的一点疑问?





© 2025-04-02 - tinynew.org. All Rights Reserved.
© 2025-04-02 - tinynew.org. 保留所有权利