所有最小生成树的实现

Question

我一直在寻找一个实现（我正在使用networkx库）来查找无向加权图的所有最小生成树（MST）。

我只能找到 Kruskal 算法和 Prim 算法的实现，两者都只返回单个 MST。

我看过解决这个问题的论文（如表示所有最小生成树及其应用于计数和生成），但是当我试图思考如何将其转化为代码时，我的头脑往往会爆炸。

实际上，我甚至找不到任何语言的实现！

- russtbarnacle

---

你需要这个做什么？我想要高效地完成这个任务并不容易，那么生成所有 n - 1 条边的子集会不会太慢了？ - IVlad

你好！不是为了重启一个旧的线程，而是我正在寻找一个（任何语言的）算法实现，可以给我一个图的所有生成树。这与你所寻找的非常相似。你有成功吗？ - rjkaplan

我也在寻找同样的东西。你找到了吗？ - Nether

@DSM 我不明白为什么这意味着它不会起作用 - 如果它不是有效的树，你可以简单地将其丢弃。这是一种枚举所有树的蛮力方法，虽然效率极低，但没有理由它不应该工作。 - IVlad

我找到了这个链接：http://www.mate.unlp.edu.ar/~liliana/lawclique_2016/07.pdf - 似乎描述了一些相对简单的算法，但是在快速阅读后，我还不能将其转化为答案。 - IVlad

Answer 1

我不知道这是否是解决方案，但它是一种解决方案（我会说这是暴力的图形版本）：

1. 使用Kruskal's或Prim's算法找到图的最小生成树。这应该是O（E log V）。
2. 生成所有的生成树。据我从两分钟的谷歌中了解，这可以在 O(Elog(V) + V + n) for n = 生成的生成树数量内完成，可能还可改进。
3. 通过树的权重等于MST的权重来过滤在步骤#2中生成的列表。这对于在步骤＃2中生成的树的数量n应该是O（n）。

注意：要偷懒！生成所有可能的树然后过滤结果将需要O（V ^ 2）内存，多项式空间需求很恶劣-生成一个树，检查其权重，如果是MST，则将其添加到结果列表中，如果不是，则丢弃它。
总时间复杂度： O（Elog（V）+ V + n）适用于具有n个生成树的G（V，E）

- Rubys

---

有趣。我在问题中提到的那篇论文有一个类似的要求，即生成所有生成树。它引用了另一篇论文《无向加权图的枚举所有生成树算法》，但我几乎又回到了找不到任何实现的状态，或者通常枚举所有生成树的状态。看来我可能不得不实现这篇论文或两篇论文才能得到解决方案。 - russtbarnacle

等等，你希望在你喜欢的编程语言中找到这个的实现？我不会抱有太大期望。你已经有了算法，现在去实施它们吧。我怀疑这不会比那更好。 - Rubys

我本来希望能找到一个“所有生成树”或“所有最小生成树”的实现，但是我在任何语言中都没有找到。所以我更惊讶的是，在任何语言中都没有实现。 - russtbarnacle

@russtbarnacle，你实现了这些算法中的任何一个吗？ - jguilhermeam

@Rubys 你如何生成所有的生成树？以及如何计算它们的总权重？我找不到相关资料。 - FaCoffee

那么，十年后我们有实现了吗？ - Danyal

Answer 2

这是一个短小的Python实现，基本上是Kruskal算法的递归变体。使用找到的第一个最小生成树的权重来限制搜索空间的大小。虽然复杂度仍然是指数级的，但比生成每个生成树要好得多。还包括一些测试代码。

[注意：这只是我自己为了乐趣和可能激发其他人对问题进一步思考的灵感而进行的实验，不是试图特别实现其他提供的答案中建议的任何解决方案的尝试]

# Disjoint set find (and collapse) 
def find(nd, djset):
    uv = nd
    while djset[uv] >= 0: uv = djset[uv]
    if djset[nd] >= 0: djset[nd] = uv
    return uv

# Disjoint set union (does not modify djset)
def union(nd1, nd2, djset):
    unionset = djset.copy()
    if unionset[nd2] < unionset[nd1]:
        nd1, nd2 = nd2, nd1

    unionset[nd1] += unionset[nd2]
    unionset[nd2] = nd1
    return unionset

# Bitmask convenience methods; uses bitmasks
# internally to represent MST edge combinations
def setbit(j, mask): return mask | (1 << j)
def isbitset(j, mask): return (mask >> j) & 1
def masktoedges(mask, sedges):
    return [sedges[i] for i in range(len(sedges)) 
            if isbitset(i, mask)]

# Upper-bound count of viable MST edge combination, i.e.
# count of edge subsequences of length: NEDGES, w/sum: WEIGHT
def count_subsequences(sedges, weight, nedges):
#{
    def count(i, target, length, cache):
        tkey = (i, target, length)
        if tkey in cache: return cache[tkey]
        if i == len(sedges) or target < sedges[i][2]: return 0
            
        cache[tkey] = (count(i+1, target, length, cache) +
            count(i+1, target - sedges[i][2], length - 1, cache) + 
            (1 if sedges[i][2] == target and length == 1 else 0))
        
        return cache[tkey]
    
    return count(0, weight, nedges, {})
#}

# Arg: n is number of nodes in graph [0, n-1]
# Arg: sedges is list of graph edges sorted by weight
# Return: list of MSTs, where each MST is a list of edges
def find_all_msts(n, sedges):
#{
    # Recursive variant of kruskal to find all MSTs
    def buildmsts(i, weight, mask, nedges, djset):
    #{
        nonlocal maxweight, msts
        if nedges == (n-1):
            msts.append(mask)
            if maxweight == float('inf'):
                print(f"MST weight: {weight}, MST edges: {n-1}, Total graph edges: {len(sedges)}")
                print(f"Upper bound numb viable MST edge combinations: {count_subsequences(sedges, weight, n-1)}\n")
                maxweight = weight
                
            return
        
        if i < len(sedges):
        #{
            u,v,wt = sedges[i]
            if weight + wt*((n-1) - nedges) <= maxweight:
            #{
                # Left recursive branch - include edge if valid
                nd1, nd2 = find(u, djset), find(v, djset)
                if nd1 != nd2: buildmsts(i+1, weight + wt,
                    setbit(i, mask), nedges+1, union(nd1, nd2, djset))
            
                # Right recursive branch - always skips edge
                buildmsts(i+1, weight, mask, nedges, djset)
            #}
        #}
    #}
        
    maxweight, msts = float('inf'), []
    djset = {i: -1 for i in range(n)}    
    buildmsts(0, 0, 0, 0, djset)    
    return [masktoedges(mask, sedges) for mask in msts]
#}

---

import time, numpy

def run_test_case(low=10, high=21):
    rng = numpy.random.default_rng()
    n = rng.integers(low, high)
    nedges = rng.integers(n-1, n*(n-1)//2)

    edges = set()
    while len(edges) < nedges: 
        u,v = sorted(rng.choice(range(n), size=2, replace=False))
        edges.add((u,v))

    weights = sorted(rng.integers(1, 2*n, size=nedges))
    sedges = [[u,v,wt] for (u,v), wt in zip(edges, weights)]
    print(f"Numb nodes: {n}\nSorted edges: {sedges}\n")
    
    for i, mst in enumerate(find_all_msts(n, sedges)):
        if i == 0: print("MSTs:")
        print((i+1), ":", mst)

if __name__ == "__main__":
    initial = time.time()
    run_test_case(20, 35)
    print(f"\nRun time: {time.time() - initial}s")

- AJ Donich

Answer 3

你可以在 Sorensen and Janssens（2005年） 的作品中找到灵感。

这个想法是按照递增顺序生成ST，一旦获得了更大的ST值，就停止枚举。

- Vitalii Vorkov

Answer 4

Ronald Rivest在Python中有一个不错的实现，mst.py

- synthesizerpatel

---

据我所知，这是一种寻找最小生成树的实现，但并非所有生成树。 - rjkaplan