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

Question

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

X 不与其他 X 关联，Y 也不与其他 Y 关联。所以情况是这样的：

左边是 Xs，右边是 Ys。

当我只有一种类型的数据时，我知道如何找到图形的连通分量：创建一个 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，但它几乎不需要内存。

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

---

双方案件

要为二部图构造邻接矩阵，您可以（最初）使用更小（仍然稀疏）B的大小|X|矩阵|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 )设置为1iff nodeX(ix)连接到 node Y(jy)。
一旦你完成构建B，你可以使用它来G简单地通过

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

请注意，我不使用zeros创建全零矩阵，但sparse这样的构造将节省内存。

现在你可以继续运行graphconncomp了G。