计算图中的森林数量：实施了吗？

Question

给定一个简单的图 G，我希望有一个函数来计算 G 中森林子图的数量。这是否已经在某些常见的编程语言中实现了，例如蟒蛇？

我做了一些谷歌搜索，但只发现了相关问题，例如计算生成树/生成森林的数量或计算森林中树木的数量。我期待在一些现有的软件包中实现它，该软件包做得相当好（考虑到问题的难度）。

Answer 1

我不知道有任何“已知”的有效算法来计算这个，但是 python 的 networkx 包确实有一个

is_forest(G)

方法，如果

true

是森林，则返回

G

。

for node in nx.connected_components(graph):
    subgraph = graph.subgraph(node)
    if nx.is_forest(subgraph):
        forest_count += 1