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

这个其实就是双指针。

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

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




  

相关话题

  机器学习到底是什么,如何使用这项技术? 
  从算法的角度来看,Elsagate 事件暴露出了「自动推荐」的哪些问题,该如何规避? 
  有哪些数学定理或者数学知识惊呆了你? 
  为什么有些算法工程师从来不谈业务,不谈解决问题,不谈价值挖掘,开口闭口就是算法模型,炼丹调参工程化? 
  怎么去实现一个简单文本编辑器? 
  如何直接跳出深层递归而不是一层一层跳出? 
  学了四年算法,码了五万行代码,但是大一期末C语言模拟及不了格怎么办? 
  二分查找有几种写法?它们的区别是什么? 
  Java对于int变量a,如何以最快速度计算34*a? 
  可以利用抄代码来同时记忆算法与练英文书法吗? 

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





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