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.代码
| 留言与评论（共有 0 条评论） “” |
