algorithm - 遍历连接的组件

Question

我想遍历包含 ~10⁷ 个顶点的无向图的每个连通分量。即我想在每个向量 V₁...V_k 上调用一些函数 f(V_i) ，其中 V_i 是一个向量，包含附加到图中第 i 个连通分量中每个节点的数据。

执行此操作最快的算法是什么？

我的第一个想法是:

1. 将所有未访问的顶点存储在一个堆中，然后重复从堆中取出一个顶点，使用DFS找到它的连通分量V_i，调用f(V_i)并从堆中删除组件中的所有顶点。
2. 找到联合查找不相交集的一个变体，它不仅支持有效的集合并集，而且可以高效地迭代集合并找到它们的成员。 (这可能吗？)

Answer 1

1. 运行经典connected components algorithm .通常，这会操纵 disjoint-sets data structure .

2. 创建一个将节点映射到节点链表的哈希表。

3. 遍历每个节点

   一个。在disjoint-sets数据结构中寻找代表节点

   必要时为哈希表中的代表节点创建一个链表

   将节点添加到代表节点关联的链表中

这需要有效的线性时间(即 Θ(|E| + |V|)，这是预期的(在广泛接受的理解下，不相交的集合实际上是线性时间)。

您现在有一个哈希表，其条目数是连接组件的数量。每个值都是连接组件中所有节点的链表。您现在可以对任何您想要的内容进行线性迭代。