查找由二部图的连通分量引起的顶点子集的算法

Question

给定一个二分图 G = (U, V, E)，我想找到所有V 的(最大)子集，它们是 G 的连通分量的一个“边”。

例如，对于关联矩阵

    0 1 0 0 0 1
    1 0 0 0 0 1
    0 0 0 0 0 0
A = 0 0 0 0 1 0
    0 0 1 0 1 0
    0 1 0 0 0 0
    0 0 0 1 0 0

行索引代表U，列索引代表V，输出应该是集合{0, 1, 5}, {2, 4}，和 {3}。

这是否等同于任何标准问题？更重要的是，有没有有效的解决方案？

Answer 1

这类似于寻找图的所有连通分量，图的边数和顶点数呈线性关系。这种方法的标准算法是对每个顶点进行广度或深度优先搜索。

除了减少与该算法相关的常量外，我认为利用图的二分性质不会加快复杂度。