問題文は次のとおりです。は、グラフはハミング距離とで構成されたクラスタリング（スタンフォードアルゴリズム - 2）
In this question your task is again to run the clustering algorithm from lecture,
but on a MUCH bigger graph.
So big, in fact, that the distances (i.e., edge costs) are only defined implicitly,
rather than being provided as an explicit list.
The data set is here. The format is:
[# of nodes] [# of bits for each node's label]
[first bit of node 1] ... [last bit of node 1]
[first bit of node 2] ... [last bit of node 2]
For example, the third line of the file
"0 1 1 0 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 1 1 0 1"
denotes the 24 bits associated with node #2.
The distance between two nodes u and v in this problem is defined as the Hamming
distance--- the number of differing bits --- between the two nodes' labels. For
example, the Hamming distance between the 24-bit label of node #2 above and the
label "0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 0 1" is 3 (since they
differ in the 3rd, 7th, and 21st bits).
The question is: what is the largest value of k such that there is a k-clustering
with spacing at least 3? That is, how many clusters are needed to ensure that no
pair of nodes with all but 2 bits in common get split into different clusters?
NOTE: The graph implicitly defined by the data file is so big that you probably
can't write it out explicitly, let alone sort the edges by cost. So you will have
to be a little creative to complete this part of the question.
For example, is there some way you can identify the smallest distances without
explicitly looking at every pair of nodes?
データセットをダウンロードすることができますhere
ここでの課題は、（Oよりも速く、グラフを作成していますn^2）。グラフには 200,000ノードがあるので、ラベルを表すために24ビットが使用されているため、グラフには2^24 = 16milのエッジが追加されるため、各エッジのハミング距離を計算できません。
バイナリデータを整数に変換してソートすると（O（nlgn）time）、int型の数値で表されるすべての頂点が現在の数値と次の数値の間にエッジを作成します。より多くのハミング距離があります。
簡体例：
今000 Let this be node A
001
010
011
100 Node B
101
110
111 Node C
、B及びC = 2で、A及びB = 1で距離をハミングし、A及びC = 3で、私はより多くの微妙がここにある知っているが、ハミング距離（ 、C）> = hammingDistance（A、B）またはhammingDistance（B、C）は常に保持されます。
このようにしてグラフを線形時間で作ることができます。このグラフを直線とノードのように表現することができます。後で、私はdisjoint tree/Union Findを使用してそれらをクラスタ化し、質問で尋ねられたクラスターの最小数を見つけることができました。
フォーラムでのテストケースはthis fileで最初の1000個のノードに対して、クラスタ数が989である、と言うが、私のプログラムは、graphInfo（）0同じエッジ、1辺があると言われます。また999 だと言われます体重1で、重量2と0エッジが実際の結果は、コードがかなり関与している
Edges with cost zero: 0
Edges with cost one: 2
Edges with cost two: 9
をしているが、そのコードをチェックするためにthisのリンクをご利用ください。私はそれが私のコードか間違っているアルゴリズムかどうかを判断することができません。
おそらく、あなたは巨大な木にプリムやkruskalsを使用し、それらを使ってユニオンを見つけることができますか？ –