算法/图表 : Maintain sets

Question

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

解析后，我需要快速地逐一迭代图的连通分量。我选择什么算法来在解析时构建连接的组件？ (在解析时，因为列出边相当昂贵)。

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

Answer 1

我想到的最简单的解决方案是一些增强的“联合查找”算法。有关基础知识，请查看 wiki article关于它或者它是由 ROBERT SEDGEWICK 在最新的 Coursera 类(class)“算法，第 1 部分”中介绍的 - 它是在“第 1 周:联合查找”期间。请查看类(class) archive (您可以免费注册)。在第 1 周的第 45 张幻灯片上，您总结了该算法的基本版本和增强版本的最坏情况时间。