前言：
眼前姐妹们对“强连通分量算法”可能比较关注，小伙伴们都想要分析一些“强连通分量算法”的相关资讯。那么小编同时在网上网罗了一些对于“强连通分量算法””的相关资讯，希望朋友们能喜欢，小伙伴们快快来学习一下吧！1.如何做到时间亚线性？
在数据量大的图中，线性算法的时间过高。连通分量数量的估计中，通过抽样，给定了最多可能访问到节点数量。设定：最多抽样次数与1/ε²同阶，每次抽样最多能访问该节点（u）所在的连通分量中2/ε个节点。
2.算法的过程
初始条件：所有抽样节点的权重值的和 = 0，以下操作重复Θ（1/ε²）次。
（1）在图中随机选择节点u
（2）从u开始BFS，访问完连通分量或者访问过2/ε个节点为止
（3）连通分量的节点数（num） = min（连通分量节点数，2/ε）
（4）节点u的权重值 = 1/num，因为对图中所有节点的权重值求和就是连通分量的数量
（5）把节点u的权重值加到所有抽样节点的权重值的和中
在重复Θ（1/ε²）次后，整个图的连通分量的个数与被抽样的节点集合的连通分量个数有比例关系：
整个图的连通分量个数 / 整个图的节点数 = 抽样节点的连通分量个数 / 抽样节点数
3.代码
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #强连通分量算法
