matlab - matlab中二分图的连通分量

Question

我有两种类型的数据，X 和 Y。X 中的每个 x 都与一定数量的 Y 相关联，Y 中的每个 y 可能与一定数量的 X 相关联，也可能不相关联。

X 不与其他 X 关联，Y 不与其他 Y 关联。所以情况看起来是这样的:

左边是 X，右边是 Y。

当我只有一种类型的数据时，我知道如何找到图形的连通分量:创建一个 N×N 矩阵并对其调用 graphconncomp。当我有两种类型的数据时，如何找到所有连接的组件？

Answer 1

如何将图的亲和矩阵构造为稀疏矩阵:

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

这将创建一个大小为 |X|+|Y|-by-|X|+|Y| 的“全零”稀疏矩阵。
如果你输入

>> whos G

您会发现，尽管 G 大约有 50K^2，但它几乎不占用内存。

现在你所要做的就是使用你的函数在X和Y的相应节点之间设置1，然后你就可以运行 G

上的 graphconncomp

---

二分法

要为二分图构建邻接矩阵，您可以(最初)使用大小为 |X| 的小得多(仍然稀疏)的矩阵 B -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 ) 设置为 1 当且仅当节点 X(ix) 连接到节点 Y (jy).
一旦你构造完了B，你就可以用它来简单地构造G

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

请注意，我不使用 zeros 来创建全零矩阵，而是使用 sparse，因此构造将节省内存。

现在你可以在 G 上运行 graphconncomp。