百科问答小站 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里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话,那么这个强连通分量就是极大强连通分量。

这个其实就是双指针。

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

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




  

相关话题

  最快的 atoi、atof 实现是什么样的? 
  你靠哪些讲解学会了曾经怎么也学不会的算法? 
  EM算法存在的意义是什么? 
  一个算法面试题,怎么写? 
  C++中开多个数组和用struct封装起来哪个速度更快? 
  1/3+1/6=计算机是如何得出0.5的? 
  对于任意既约分数,都可以分解成有限个不同奇数的倒数和吗? 
  如何看待 2022 年秋招算法岗竞争如此激烈? 
  在校生为了面试,有必要强行记住一些复杂算法如红黑树、KMP等的实现吗? 
  如何用最省内存的方法表示0-9的十个字符? 

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





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