确定数据集中离散图数量的算法

Question

我有一个数据集，其中包含顶点及其连接到的其他顶点。该数据集表示一个无向图。我想要确定的是该数据集中存在多少个不连通的离散图。

例如下面的数据（顶点，连接顶点的数组）将表示两个不连通的离散图：

123,[567,345]
345,[123,567,789]
567,[123,345]
789,[345]
321,[987]
987,[321]

在这样一个小的数据集上，我很容易想象出答案的方法，但是当我将其扩展到数亿个顶点的数据集时，我不确定是否有任何非常高效的方法。 我倾向于做一些可以在Hadoop上运行的事情，但无论是直接编写MapReduce作业还是使用像Giraph或Faunus这样的工具，我都希望能得到一些建议。

谢谢。

- Nick

---

我认为你指的是图的不连通组件。为了实现这一点，可以迭代地从未访问过的顶点开始BFS，保持一个计数器，每次启动新的BFS时将其增加一，并使用该计数器标记已访问顶点的节点。最终，您将拥有连接组件的数量以及将它们分成这些组件的顶点的标记。 - G. Bach

查看Tarjan算法 - user1406062

Answer 1

正如巴赫在评论中所说，这个问题，即“识别连通组件”，通常通过普通的广度优先搜索来解决。Skiena给出了基本算法如下：

connected_components( graph *g ){
   int c, i; /* component number and counter */
   initialize_search( g );
   c = 0;
   for( i = 1; i <= g->num_vertices; i++ ){
      if( discovered[i] == FALSE ){
         c += 1;
         printf( "component %d: ", c );
         bfs( g, i );  // breadth first search
         printf( "\n" );
      }
    }
}

- Tyler Durden

---

这对于他所询问的“数亿个顶点”是行不通的。 - pkacprzak

@pkacprzak 如果他没有提到任何已经发生的预处理，那么他如何能够在至少查看每条边一次的情况下计算连通分量呢？在没有先前知识的情况下，线性时间是他所能做到的最好的。 - G. Bach

@G.Bach 当然，线性时间是最好的，我的意思是他不能使用上面的代码。他怎么能在内存中存储已发现的数组呢？ - pkacprzak

@pkacprzak 100,000,000 * 8 字节 = 800 MB，这是很多的，但如果他可以将图形本身存储在内存中，那么他可能还可以再节省另外 800MB 的空间（8 字节相当宽裕，我不确定他使用的是哪种语言以及在他选择的语言中 int 数组占用多少空间）。不过，他最好使用数据库。 - G. Bach

这就是你要做的。并不存在能够让你比处理小数量的顶点更轻松地解决大量顶点的神奇公式。如果你遇到了内存问题，你必须将其缓存至磁盘并加以处理。 - Tyler Durden

当然，这就是为什么他应该倾向于使用MapReduce而不是顺序算法的原因。 - pkacprzak