3

X と Y の 2 種類のデータがあります。X のすべての x はいくつかの Y に関連付けられており、Y のすべての y はいくつかの X に関連付けられている場合と関連付けられていない場合があります。

X は他の X と関連付けられず、Y は他の Y と関連付けられません。したがって、状況は次のようになります。

接続されたコンポーネント

左が X、右が Y です。

1 種類のデータしかない場合に、グラフの連結要素を見つける方法を知っています。つまり、N 行 N 列の行列を作成し、それを呼び出しますgraphconncomp。2 種類のデータがある場合、すべての連結要素を見つけるにはどうすればよいですか?

4

1 に答える 1

3

グラフの親和性行列を疎行列として構築する方法:

G = sparse( length(X)+length(Y), length(X)+length(Y) );

|X|+|Y|これにより、サイズが-by-の「すべてゼロ」のスパース行列が作成され|X|+|Y|ます。
入力すると

>> whos G

G約 50K^2 の容量があるにもかかわらず、ほとんどメモリを必要としないことがわかります。

Xあとは、関数を使用してとの対応するノード間に 1 を設定するだけで、実行できるようにYなりますgraphconncompG

二部ケース

2 部グラフの隣接行列を作成するには、(最初に)Bサイズが|X|-by-のはるかに小さい (まだまばらな) 行列を使用できます|Y|。x=length(X)とy=length(Y)、次に

 B = sparse( x, y ); % if you have an estimate of the number of edges, you can preallocate here

ノードがノードに接続されている場合、エントリB( ix, jy )は に設定されます。 の構築が完了したら、それを使用して、次のように簡単に形成できます。1X(ix)Y(jy)
BG

 G = [ sparse( x, x ), B; B.', sparse(y, y)];

zerosすべてゼロの行列を作成するために使用しないことに注意してください。そのsparseため、構築はメモリ効率が高くなります。

で実行できるようgraphconncompになりましたG。

于 2013-11-18T19:49:04.193 に答える