时间戳

首页 > 解决方案 > 在 Python 中使用 networkx 列出所有生成树

python - 在 Python 中使用 networkx 列出所有生成树

问题描述

我需要一种方法来获取 Python 中给定图形的所有生成树。我正在使用networkx，它可以获得最小权重树，但我需要所有可能的生成树（作为列表、生成器或其他）。有没有一种简单的方法可以做到这一点？

编辑：澄清一下，我知道它的计算成本很高，我只需要它来处理小图（最多 7-10 个顶点）。

标签： pythongraphnetworkx

解决方案

我最终编写了以下代码。

def spanning_trees(G):
        
        def build_tree(H, edges):
            if H.is_connected():
                yield H
            else:
                for i in range(len(edges)):
                    if edges[i][1] not in nx.algorithms.descendants(H, edges[i][0]):
                        H1 = Graph(H)
                        H1.add_edge(*edges[i])
                        for H2 in build_tree(H1, edges[i+1:]):
                            yield H2

        E = Graph()
        E.add_nodes_from(G)
        return build_tree(E, [e for e in G.edges])

它可以很容易地处理 8 个顶点上的完整图，但我不是编码专家，所以可能有一些优化空间。有什么建议吗？

推荐阅读