遍历连接的组件

Question

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

最快的算法是什么？

我的第一个想法是：

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

Answer 1

运行经典connected components algorithm. Typically, this manipulates a disjoint-sets data structure.
创建一个散列 table 映射节点到节点链表。
迭代每个节点

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

b。为hash中的代表节点创建链表table，如果需要

c。将节点加入代表节点关联的链表

这需要有效的线性时间（即，Θ(|E| + |V|)，预期（根据广泛接受的理解，不相交的集合是有效的线性时间）。

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

Answer 2

是的，DFS 是一个不错的选择。但请记住，对于给定范围的 10^7 个节点，如果您运行一个递归 DFS，您可能会遇到内存问题。因为在麦芽汁情况下，所有节点都会形成一条链，您将需要巨大的堆栈，导致 Whosebug( :D )

尝试做：

DFS 使用顺序为 O(V+E) 的堆栈（非递归 DFS）或，
简单使用 BFS（考虑简单性和节点数量的最佳选择）order(V+E)

BFS 通常用于最短路径问题，但它可以用于许多其他应用程序，例如这个应用程序。这将从堆中获取 space 作为队列数据结构，其中通常的递归 DFS 从堆栈中获取 space。

Answer 3

如果将图存储为邻接表并且顶点用从 1 到 n-1 的整数表示，则不需要联合查找或哈希表。

我们假设 g[v] 是与 v 相邻的顶点列表（向量）。此外，设 cc 为列表的列表（向量的向量），其中 cc[i] 表示 i-th 连通分量中的顶点。出于实现目的，当且仅当我们在 DFS 例程中检查了 v 时，让 visited[v] = true 我们将要使用。然后伪代码看起来像这样：

dfs(v, current_cc):
   visited[v] = true
   current_cc.append(v)
   for u in g[v]:
      if not visited[u]:
         dfs(u, current_cc)

for v = 0 to n-1:
   visited[i] = false

for v = 0 to n-1:
   if not visited[v]:
      current_cc = []
      dfs(v, current_cc)
      cc.append(current_cc)

//From now, cc[i] is a list of vertices in the i-th connected component, 
//so we can easily iterate and call whatever we want on them.

遍历连接的组件

iterating over connected components

algorithm

data-structures

connected-components