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

Question

我有一个数据集，其中包含顶点和它们连接的其他顶点。该数据集表示一个无向图。我要确定的是数据集中存在的离散断开图的数量。

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

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

在这么小的数据集上，我很容易想出让我得到答案的方法，但是当我将其扩展到具有数亿个顶点的数据集时，我不确定我是否有任何非常高效的。我倾向于做一些可以在 Hadoop 上运行的东西，但是天气是直接编写 MapReduce 作业或使用 Giraph 或 Faunus 之类的东西，我很想得到一些建议。

谢谢。

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" );
      }
    }
}