3

頂点とそれらが接続されている他の頂点を含むデータセットがあります。このデータセットは無向グラフを表します。私が決定しようとしているのは、データセット内に存在する目立たない切断されたグラフの数です。

たとえば、以下のデータ (頂点、接続された頂点の配列) は、2 つの個別の切断されたグラフを表します。

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

このような小さなデータ セットでは、答えにたどり着く方法を想像するのは非常に簡単ですが、これを数億の頂点を持つデータ セットにスケールアップすると、非常に重要なものがあるかどうかわかりません。効率的。私は Hadoop で実行できる何かを行うことに傾倒していますが、MapReduce ジョブを直接記述したり、Giraph や Faunus のようなものを使用したりする場合は、アドバイスをもらいたいです。

ありがとう。

4

1 に答える 1

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" );
      }
    }
}
于 2013-06-17T17:47:15.287 に答える