百科问答小站 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+1 个岛,有多少种连法? 
  要设计一段C++程序将这组数按要求重新排序时,有哪些好的算法? 
  如何计算一局三国杀所进行的回合数的数学期望? 
  如何检验算法的正确性? 
  链表求交集,从链表头删去一长串而非一个节点?(已解决)? 
  如何看待两次 IOI 金牌,一次 ACM 全球总决赛亚军的清华大学计算机系毕业生去高中当信息学教师? 
  李彦宏批评推荐式算法,你怎么看? 
  如何学习视频识别技术? 
  怎么证明每个位上的数字之和可以被3整除的数可以被3整除? 
  刚进算法团队,大牛们讨论高深的cv术语和算法,如何才能听懂? 

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





© 2025-03-31 - tinynew.org. All Rights Reserved.
© 2025-03-31 - tinynew.org. 保留所有权利