Перечислить все связующие деревья с networkx в Python

Question

Мне нужен способ получить все остовные деревья данного графа в Python. Я использую networkx, он может получить дерево минимального веса, но мне нужны все возможные остовные деревья (в виде списка, генератора или чего-то еще). Есть ли простой способ сделать это?

РЕДАКТИРОВАТЬ: Чтобы уточнить, я знаю, что это затратно с точки зрения вычислений, мне это нужно только для небольших графов (максимум 7-10 вершин).

Answer 1

В итоге я написал следующий код.

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 вершинах, но я не эксперт в кодировании, поэтому, вероятно, есть место для оптимизации . Есть предложения?