在多项式时间内测试无向图是否为森林(由树组成)

Question

我目前正在学习森林，我对这个问题感到困惑。检验无向图是否是森林(即无环图或不相交树的并集(的问题是否属于可以在多项式时间内解决的问题的复杂度类P？

Answer 1

线性时间有很多方法可以做到这一点。

对于大多数图形表示，最简单的方法是基于以下观察：N 个节点的连接组件是一棵树，因为它正好有 N-1 条边。

因此，只需使用 DFS、BFS、传递闭包或其他方法找到连接的组件，计算沿途的节点和边，并确保计数正确。

Answer 2

是的，事实上，这可以使用深度优先搜索在线性时间内完成，或者使用联合查找数据结构在非常接近线性的时间内完成。后者要简单得多，所以这里有一个例子：输入edges是节点对的列表。

def is_forest(edges):
uf = UnionFind()
for a, b in edges:
if uf.find(a) == uf.find(b):
return False
uf.union(a, b)
return True

使用最优数据结构，时间复杂度为 O(n α(n((，其中n是边数，α 是非常缓慢增长的逆阿克曼函数。