有人知道在二分图中找到最大独立顶点集的暴力算法的通用概要吗？
我知道还有其他算法，比如König定理来找MIS，但我想知道暴力方法的伪代码是什么？
此外，这种暴力算法的运行时间复杂度是多少？
暴力算法是遍历所有顶点集并检查它们是否独立。有2^n个顶点集，遍历所有边以检查独立性是O(m)的，因此这样的算法成本为O(2^n*m)。
2^n
O(m)
O(2^n*m)
n
m
n * (n-1) / 2
O(2^n * n * (n-1)/2)
2^n个子集，则n必须是顶点的数量。m的最大值为n * (n-1) / 2，因此作为顶点数量函数的复杂度变为O(2^n * n * (n-1)/2)。 - fnisi