图 - 最小生成树算法 - Prim、Kruskal 算法

图 - 最小生成树算法 - Prim、Kruskal 算法

一、引言

在图论中，最小生成树（Minimum Spanning Tree，MST）是一个重要的概念。对于一个带权连通无向图，最小生成树是一棵包含图中所有顶点的树，并且树中所有边的权值之和最小。最小生成树在很多实际问题中都有广泛的应用，比如在通信网络的布线问题中，要使所有节点都连通且布线成本最低；在交通网络的规划中，要以最小的建设成本连接各个城市等。本文将详细介绍两种经典的最小生成树算法：Prim 算法和 Kruskal 算法。

二、Prim 算法

（一）算法思想

Prim 算法是一种贪心算法，它从图中的任意一个顶点开始，逐步扩展生成树。每次选择一条连接已在生成树中的顶点和不在生成树中的顶点的边，且这条边的权值最小，将这条边和对应的顶点加入到生成树中，直到所有顶点都被加入到生成树中。

（二）算法步骤

1. 选择一个起始顶点，将其加入到生成树中。
2. 重复以下步骤，直到所有顶点都被加入到生成树中：
   • 从连接生成树中的顶点和非生成树中的顶点的所有边中，选择一条权值最小的边。
   • 将这条边和对应的非生成树中的顶点加入到生成树中。

（三）代码示例（Python）

import sys
def prim(graph):
    num_vertices = len(graph)
    # 用于记录每个顶点是否已被加入到生成树中
    visited = [False] * num_vertices
    # 用于记录每个顶点到生成树的最小权值
    key = [sys.maxsize] * num_vertices
    # 用于记录每个顶点的父节点
    parent = [-1] * num_vertices
    # 选择第一个顶点作为起始顶点
    key[0] = 0
    for _ in range(num_vertices):
        # 找到未被访问且权值最小的顶点
        min_key = sys.maxsize
        min_index = -1
        for v in range(num_vertices):
            if not visited[v] and key[v] < min_key:
                min_key = key[v]
                min_index = v
        # 将该顶点标记为已访问
        visited[min_index] = True
        # 更新与该顶点相邻的顶点的权值和父节点
        for v in range(num_vertices):
            if graph[min_index][v] > 0 and not visited[v] and graph[min_index][v] < key[v]:
                key[v] = graph[min_index][v]
                parent[v] = min_index
    # 输出最小生成树的边和权值
    result = []
    for i in range(1, num_vertices):
        result.append((parent[i], i, graph[i][parent[i]]))
    return result
# 示例图的邻接矩阵表示
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
mst = prim(graph)
print("Prim 算法得到的最小生成树的边和权值：")
for edge in mst:
    print(f"边: ({edge[0]} - {edge[1]}), 权值: {edge[2]}")

（四）复杂度分析

• 时间复杂度：$O(V^2)$，其中 $V$ 是图中顶点的数量。如果使用优先队列（堆）来优化选择最小权值边的过程，时间复杂度可以降低到 $O((V + E)\log V)$，其中 $E$ 是图中边的数量。
• 空间复杂度：$O(V)$，主要用于存储每个顶点的访问状态、最小权值和父节点。

三、Kruskal 算法

（一）算法思想

Kruskal 算法也是一种贪心算法，它的基本思想是将图中的所有边按照权值从小到大进行排序，然后依次选择权值最小的边，如果这条边加入到生成树中不会形成环，则将其加入到生成树中，直到生成树包含图中所有顶点。

（二）算法步骤

1. 将图中的所有边按照权值从小到大进行排序。
2. 初始化一个空的生成树。
3. 依次选择权值最小的边：
   • 如果这条边加入到生成树中不会形成环，则将其加入到生成树中。
   • 重复步骤 3，直到生成树包含图中所有顶点。

（三）代码示例（Python）

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):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x!= root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
            return True
        return False
def kruskal(graph):
    num_vertices = len(graph)
    edges = []
    # 提取所有边
    for i in range(num_vertices):
        for j in range(i + 1, num_vertices):
            if graph[i][j] > 0:
                edges.append((i, j, graph[i][j]))
    # 按权值从小到大排序
    edges.sort(key=lambda x: x[2])
    uf = UnionFind(num_vertices)
    mst = []
    for edge in edges:
        u, v, weight = edge
        if uf.union(u, v):
            mst.append(edge)
    return mst
# 示例图的邻接矩阵表示
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]
mst = kruskal(graph)
print("Kruskal 算法得到的最小生成树的边和权值：")
for edge in mst:
    print(f"边: ({edge[0]} - {edge[1]}), 权值: {edge[2]}")

（四）复杂度分析

• 时间复杂度：$O(E\log E)$，其中 $E$ 是图中边的数量。主要的时间开销在于对边进行排序。
• 空间复杂度：$O(E)$，主要用于存储所有的边。

四、两种算法的比较

五、总结

Prim 算法和 Kruskal 算法是两种经典的最小生成树算法，它们都基于贪心策略，通过不同的方式逐步构建最小生成树。在实际应用中，需要根据图的特点（稠密图或稀疏图）来选择合适的算法。如果图是稠密图，Prim 算法可能更合适；如果图是稀疏图，Kruskal 算法可能更高效。通过理解和掌握这两种算法，我们可以解决很多与最小生成树相关的实际问题。