1

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

最快的算法是什么？

我的第一个想法是：

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

3 回答 3

1

  1. 运行经典的连通分量算法。通常，这会操纵一个不相交的数据结构。

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

  3. 遍历每个节点

    一种。在不相交集数据结构中找到代表节点

    湾。如有必要，为哈希表中的代表节点创建链表

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

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

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

于 2016-10-04T13:26:30.793 回答
0

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

尝试做：

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

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

于 2016-10-04T13:55:36.977 回答
0

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

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

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.
于 2016-10-04T14:02:21.997 回答