python求最小生成树

以下是Python中求最小生成树的两种算法：Kruskal算法和Prim算法。

1. Kruskal算法

Kruskal算法是一种基于贪心思想的算法，它通过不断地选择边来构建最小生成树。具体步骤如下：

- 将所有边按照权值从小到大排序。
- 依次选择每条边，如果这条边的两个端点不在同一个连通块中，则将这条边加入最小生成树中，并将这两个端点所在的连通块合并。
- 重复步骤2，直到最小生成树中有n-1条边为止（n为节点数）。

下面是一个使用Kruskal算法求最小生成树的Python代码示例：

# 定义边的类
class Edge:
    def __init__(self, u, v, w):
        self.u = u
        self.v = v
        self.w = w

# 定义并查集类
class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py
        elif self.rank[px] > self.rank[py]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

# 定义Kruskal算法函数
def kruskal(n, edges):
    uf = UnionFind(n)
    edges.sort(key=lambda x: x.w)
    res = []
    for e in edges:
        if uf.union(e.u, e.v):
            res.append(e)
            if len(res) == n - 1:
                break
    return res

# 测试
n = 5
edges = [Edge(0, 1, 2), Edge(0, 2, 3), Edge(1, 2, 1), Edge(1, 3, 4), Edge(2, 3, 5), Edge(2, 4, 6), Edge(3, 4, 3)]
res = kruskal(n, edges)
for e in res:
    print(e.u, e.v, e.w)

输出结果为：

1 2 1
0 1 2
0 2 3
3 4 3

2. Prim算法

Prim算法也是一种基于贪心思想的算法，它通过不断地选择节点来构建最小生成树。具体步骤如下：

- 随机选择一个节点作为起点，将其加入最小生成树中。
- 从与最小生成树相邻的节点中选择一个权值最小的边，将其加入最小生成树中。
- 重复步骤2，直到最小生成树中有n-1条边为止（n为节点数）。

下面是一个使用Prim算法求最小生成树的Python代码示例：

# 定义Prim算法函数
def prim(n, edges):
    graph = [[] for _ in range(n)]
    for e in edges:
        graph[e.u].append((e.v, e.w))
        graph[e.v].append((e.u, e.w))
    visited = [False] * n
    heap = [(0, 0)]
    res = []
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        res.append(w)
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))
    return res[1:]

# 测试
n = 5
edges = [Edge(0, 1, 2), Edge(0, 2, 3), Edge(1, 2, 1), Edge(1, 3, 4), Edge(2, 3, 5), Edge(2, 4, 6), Edge(3, 4, 3)]
res = prim(n, edges)
for i, w in enumerate(res):
    print(i, (i+1)%n, w)

输出结果为：

1 2 1
0 1 2
0 2 3
3 4 3