如何高效生成一个图的所有可能生成树

Question

请注意，本问题并非询问MST，而是询问所有可能的生成树。

因此，这与查找所有最小生成树或所有最小生成树实现不同。

---

我只需要从图中生成所有可能的 生成树。

我认为暴力方法是直接的：

假设我们有 V 个节点和 E 条边。

1. 获取图的所有边
2. 获取 E 条边中的所有可能的 V-1 组合。
3. 从组合中过滤出 非生成树（对于一棵生成树，一个集合内的所有节点应该恰好出现一次）

但我认为在面对大图时速度太慢了。

我们有更好的方法吗？

- Jackson Tale

---

实际上，你链接的算法在将所有边权重设置为相同值后将适用于你。权重的最明显选择是1或0，但这完全无关紧要（除非存在溢出问题）。 - G. Bach

@G.Bach，您能否将您的评论转换为答案？ - Jackson Tale

Answer 1

将所有边的权重设置为相同的值，然后使用算法找到所有最小生成树。

由于所有生成树都有|V|-1条边且所有边的权重相等，因此所有生成树都是最小生成树。

- G. Bach

---

我认为这是一个正确的答案，但它让我想起了关于数学家煮水的笑话，因为我所知道的所有最小生成树枚举算法都会枚举出安全边子图中的所有生成树。 - David Eisenstat

@DavidEisenstat 我从未看过任何枚举MST的算法，所以只有将其视为黑匣子，显而易见的方法就是我的答案。虽然我喜欢那个笑话，但不确定它是在嘲笑工程师还是数学家，或者两者都是。编辑：感谢那个网站，我已经有一段时间没有笑过了。 - G. Bach

@DavidEisenstat 你有更好的想法吗？ - Jackson Tale

@JacksonTale 我不知道有哪些枚举最小生成树的算法，但考虑到David所知道的所有算法都会枚举某个子集的所有生成树，你可能需要详细查看这些算法，并且只需放弃限制算法为安全边的限制。 - G. Bach

@JacksonTale 我不知怎么会认为 David Eppstein 在1995年发表的文章（http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.8848）比它实际上简单。Knuth 的 TAoCP 第4卷中有一个生成 Knuth 树的算法。 - David Eisenstat

Answer 2

我对这个问题产生了兴趣，但还没有找到一个真正令人满意的答案。然而，我找到了一些参考资料：Knuth在TAOCP第4卷第4部分中的算法S和S'，Sorensen和Janssens的一篇论文paper by Sorensen and Janssens，以及Knuth的GRAYSPAN、SPSPAN和GRAYSPSPAN。可惜它们都不是我能使用的语言实现...我想我将不得不花些时间编写它们...

- Edward Doolittle

Answer 3

你可以使用收缩删除算法来生成无向图的所有生成树。在GitHub上有一个名为Spanning Trees Generator的快速Python代码。

from itertools import product
import networkx as nx 
import numpy as np 
import matplotlib.pyplot as plt

#Optional: Calculate the total number of spanning trees for a given graph (g) using the Matrix Tree Theorem (Kirchhoff's theorem),
def numSpanTrees(g)-> int:
    if not nx.is_connected(g):
        print("Only for connected graphs")
        return 0
    if nx.is_directed(g): nx.to_undirected(g)
    n = g.number_of_nodes()
    laplacian_matrix = nx.laplacian_matrix(g).toarray() #Calculate the Laplacian matrix
    cofactor_matrix = laplacian_matrix[1:n, 1:n]  # Choose any cofactor by excluding the first row and column
    determinant = np.linalg.det(cofactor_matrix)  #Calculate the determinant of an cofactor of Laplacian matrix
    return int(np.round(abs(determinant)))
#Generate all spanning trees using contraction-deletion algorithm:
def spanTrees(trs, Edg, all_span_trees, k):
    if k == 0:
        all_span_trees.extend(product(*trs))#Expand parallels edges using the Cartesian product
    
    for i in range(k):
        if Edg[k][i] == []: continue
        trs.append(Edg[k][i])
        Edg[i] = [Edg[i][j] + Edg[k][j] for j in range(i)]#Contraction 
        spanTrees(trs, Edg, all_span_trees, k-1)
        trs.pop()
        [Edg[i][j].pop() for j in range(i) for _ in range(len(Edg[k][j]))]#Deletion
#Helper function
def Spanning_Trees_Generator(g, hch = False):
    if not nx.is_connected(g):
        print("Only for connected graphs")
        return 0
    if nx.is_directed(g): nx.to_undirected(g)
    n = g.number_of_nodes()
    edgs = list(g.edges)
    Edg = [[[] for _ in range(n)] for _ in range(n)]
    mx = len(edgs)
    edgNum = dict() #dictionary designed to store labeled edges where the keys are integer labels for the edges, and the values are tuples representing the ordinary edge definitions (in, out)

    for ed in edgs:
        i, j = sorted(ed)
        Edg[j][i] = [mx]
        edgNum[mx] = ed
        mx -= 1
    all_span_trees = []
    spanTrees([], Edg, all_span_trees, n-1)
  
    if hch:  
        return all_span_trees #Generate only the labeled edges (Keys) 
    else:
        return [nx.Graph(edgNum[k] for k in element) for element in all_span_trees] #Generate spanning trees as NetworkX graphics objects

# Example usage
g = nx.complete_graph(5)
print("Number of Spanning Trees : ", numSpanTrees(g)) #Optional and only for undirected graph
spanTreesGraph = Spanning_Trees_Generator(g)
        
#Plot the first spanning tree
pos = nx.circular_layout(g)
nx.draw(g, pos, with_labels=True, node_color='lightblue', node_size=200, edge_color='b')
nx.draw(spanTreesGraph[0], pos, with_labels=True, node_color='lightgreen', node_size=200, edge_color='r')
plt.show()

https://github.com/tagtog12000/SpanTree/blob/master/Spanning%20Trees%20Generator.py

- Tag Mohamed Amine

---

虽然这个链接可能回答了问题，但最好在这里包含答案的关键部分，并提供链接作为参考。仅有链接的答案如果链接页面发生变化，可能会变得无效。- 来自审核 - undefined

好的，完成了。我的代码已经添加到答案中。 - undefined