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

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

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

我不认为通过利用图的二分性来提高复杂性，除了减少与该算法相关的常数。