算法查找由两分图的连接组件诱导的顶点子集

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 ，输出应为sets {0，1，5}，{2，4}，和{3}。

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

Answer 1

这类似于找到图的所有连接组件，该图是边缘和顶点的线性。这种方法的标准算法是在每个顶点上进行广度或深度搜索。

我认为，除了减少与此算法相关的常数外，没有利用图形的两分性质来提高复杂的速度。