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

这个其实就是双指针。

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

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




  

相关话题

  到了 2022 年,人工智能有哪些真正可落地的应用? 
  刚进算法团队,大牛们讨论高深的 cv 术语和算法,如何才能听懂? 
  数据结构与算法在工作的作用及其大学学到什么程度才算可以? 
  高斯模糊的原理是什么,怎样在界面中实现? 
  算法和算法策略是一个意思吗? 
  Auto X的自动驾驶技术用了什么技术? 
  任何密码都可以用穷举推算出来,只是时间问题。如果是这样的话,那不是很不安全? 
  目标检测算法中Two-stage算法速度慢,到底在哪里? 
  如何看待 2020 届校招算法工程师岗位求职人数远大于招聘岗位的现象? 
  网上常能见到的一段 JS 随机数生成算法如下,为什么用 9301, 49297, 233280 这三个数字做基数? 

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





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