生成树

生成树（Spanning Tree）是一个连通图的生成树是图的极小连通子图，它包含图中的所有顶点，并且只含尽可能少的边。这意味着对于生成树来说，若砍去它的一条边，则会使生成树变成非连通图；若给它增加一条边，则会形成图中的一条回路。

最小生成树

最小生成树（Minimum Spanning Tree，简称 MST）是一个图的生成树中，边的权重之和最小的那棵生成树。
对于一个带权连通无向图G=（V，E），生成树不同，每棵树的权（即树中所有边上的权值之和）也可能不同。设X为G的所有生成树的集合，若T为X中边的权值之和最小的那棵生成树，则T称为G的最小生成树（Minimum-Spanning-Tree(MST),在一个加权连通图中，可能存在多个不同的生成树，但是其中只有一个最小生成树。最小生成树通常用于解决网络设计、通信网络等问题。

不难看出，最小生成树具有如下性质:
1）最小生成树不是唯一的，即最小生成树的树形不唯一，X中可能有多个最小生成树。当图G中的各边权值互不相等时，G的最小生成树是唯一的；若无向连通图G的边数比顶点数少1，即G本身是一棵树时，则G的最小生成树就是它本身。
2）最小生成树的边的权值之和总是唯一的，虽然最小生成树不唯一，但其对应的边的权值之和总是唯一的，而且是最小的。
3）最小生成树的边数为顶点数减1

构造最小生成树有多种算法，但大多数算法都利用了最小生成树的下列性质：假设G=（V，E)是一个带权连通无向图，U是顶点集V的一个非空子集。若(u,v)是一条具有最小叔值的边，其中u∈U， v∈V- U，则必存在一棵包含边(u,V)的最小生成树，基于该性质的最小生成树算法主要有Prim算法和Kruskal算法，它们都基于贪心算法的策略。

常用的最小生成树算法

Prim算法：Prim算法是一种贪心算法，从一个顶点开始，每次选择权重最小的边来扩展最小生成树，直到所有顶点都加入到最小生成树中为止。

Kruskal算法：Kruskal算法是一种基于并查集的贪心算法，它首先将所有边按权重从小到大排序，然后依次考虑每条边，如果当前边连接的两个顶点不在同一个连通分量中，则将这条边加入最小生成树中，并将这两个顶点合并到同一个连通分量中，直到最小生成树的边数达到n-1为止。

最小生成树算法的选择：
如果图的边数量比较少，那么Kruskal算法通常更加简洁高效。
如果图的顶点数量比较少，那么Prim算法可能更容易实现和理解。
如果图是稠密图（边数量接近于完全图），那么Prim算法的时间复杂度可能更低，因为Prim算法在每一步都只需要考虑与当前最小生成树相邻的边。

from heapq import heappop, heappush

# Prim算法
def prim(graph):
    n = len(graph)
    visited = [False] * n
    min_heap = [(0, 0)]  # (权重, 顶点)
    mst_weight = 0
    while min_heap:
        weight, node = heappop(min_heap)
        if visited[node]:
            continue
        visited[node] = True
        mst_weight += weight
        for neighbor, weight in graph[node]:
            if not visited[neighbor]:
                heappush(min_heap, (weight, neighbor))
    return mst_weight

# Kruskal算法
def kruskal(graph):
    n = len(graph)
    parent = list(range(n))
    edges = []
    mst_weight = 0
    for u in range(n):
        for v, weight in graph[u]:
            edges.append((weight, u, v))
    edges.sort()
    for weight, u, v in edges:
        if find(u, parent) != find(v, parent):
            union(u, v, parent)
            mst_weight += weight
    return mst_weight

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)
    return parent[x]

def union(x, y, parent):
    root_x = find(x, parent)
    root_y = find(y, parent)
    parent[root_x] = root_y

# 测试
graph = [
    [(1, 1), (2, 2)],
    [(0, 1), (2, 4), (3, 5)],
    [(0, 2), (1, 4), (3, 3)],
    [(1, 5), (2, 3)]
]

print("Prim算法最小生成树权重：", prim(graph))
print("Kruskal算法最小生成树权重：", kruskal(graph))

参考链接:https://zhuanlan.zhihu.com/p/136387766