算法/图:维护集

Question

在应用程序中，我正在逐个读取无向图的顶点，只有当两个顶点都出现时，边才变得明显。

解析后，我需要快速迭代图的连接组件。我所选择的在解析时建立连接组件的算法是？(在解析时，因为列出边缘非常昂贵)。

我有250个顶点，很难判断每个顶点的边数，但假设它被限制在100 (也就是说，我们有<< 250 * 100 /2= 12500条边)。我还想知道一个较低的边缘计数(比如说500)将如何影响算法的选择。(是的，250个顶点并不多，但是在这个应用程序中，即使是小的加速比计数--算法运行了很多次)。

Answer 1

我想到的最简单的解决方案是一些增强的“联合查找”算法。关于基础知识，请看一下wiki文章，或者它是由ROBERT教授的最新课程“算法，Part1”--这是在“第一周:联合-查找”期间提出的。请查看归档类(您可以免费注册)。在第一周的幻灯片45中，您总结了此算法的基本版本和增强版本的最坏情况时间。