数据结构：最小生成树—Prim（普里姆）与Kruskal（克鲁斯卡尔）算法

最小生成树（MST）算法详解 👣

一、引言 👀

1. 问题背景 👂

在图论中，最小生成树（Minimum Spanning Tree, MST） 是指在一个连通加权无向图中，找到一棵包含所有顶点的生成树，并且所有边的权值之和最小。MST 在现实世界中有广泛的应用，例如：

• 网络设计（如光纤布线、通信网络优化）
• 电路布线（减少电路板连接成本）
• 交通规划（优化城市道路或铁路连接）

为什么需要最小生成树？
在连通图中，可能存在多条路径连接所有节点，但不同的边权值（如距离、成本）不同。MST 的目标是找到总成本最低的连接方式，避免冗余连接，提高效率。

2. 算法概览 👃

目前最经典的两种 MST 算法是 Prim 算法 和 Kruskal 算法，它们均采用贪心策略，但在实现方式上有所不同：

二、基础概念回顾 👅

1. 图的术语 👄

• 连通图：任意两个顶点之间都存在路径。
• 加权图：每条边都有一个权值（如距离、成本）。
• 生成树：包含图中所有顶点的无环连通子图。

2. 贪心算法思想 💋

贪心算法在每一步选择当前最优解，最终希望达到全局最优。Prim 和 Kruskal 算法都基于贪心策略：

• Prim：每次选择连接已选顶点和未选顶点的最小边。
• Kruskal：每次选择全局最小且不构成环的边。

三、Prim 算法详解 👓

1. 算法思想 👔

Prim 算法从一个顶点出发，逐步扩展 MST，每次选择连接已选顶点集和未选顶点集的最小权值边，直到覆盖所有顶点。

2. 图解示例 👕

3. 算法步骤 👖

1. 初始化：任选一个顶点作为起点，加入 MST 集合。
2. 重复操作：
   • 找到连接已选顶点集和未选顶点集的最小权值边。
   • 将该边加入 MST，并将新顶点加入已选集合。
3. 终止条件：所有顶点均被包含。

4. 代码实现（伪代码） 👗

def prim(graph):
    MST = set()
    visited = {random_vertex}  # 随机选择一个起点
    while len(visited) < len(graph.vertices):
        min_edge = find_min_edge_between(visited, graph)
        MST.add(min_edge)
        visited.add(min_edge.new_vertex)
    return MST

5. 复杂度与适用场景 👘

• 时间复杂度：
  • 普通实现：$O(V^2)$（适合邻接矩阵稠密图）。
  • 优先队列优化：$O(ElogV)$（适合邻接表存储的图）。
• 适用场景：适合边数较多的稠密图（如完全图）。

四、Kruskal 算法详解 👙

1. 算法思想 👚

Kruskal 算法按边权从小到大排序，逐步选择最小边，并确保不形成环（使用并查集检测）。

2. 图解示例 👛

3. 算法步骤 👜

1. 边排序：将所有边按权值升序排列。
2. 初始化并查集：每个顶点自成一个集合。
3. 遍历边：依次选择最小边，若两端点不在同一集合，则加入 MST 并合并集合。

4. 代码实现（伪代码）👝

def kruskal(graph):
    MST = set()
    edges_sorted = sort(graph.edges)  # 按边权排序
    uf = UnionFind(graph.vertices)    # 初始化并查集
    for edge in edges_sorted:
        if uf.find(edge.u) != uf.find(edge.v):  # 检查是否成环
            MST.add(edge)
            uf.union(edge.u, edge.v)
    return MST

5. 复杂度与适用场景 🎒

• 时间复杂度：$O(ElogE)$（主要由排序决定）。
• 适用场景：适合边较少的稀疏图（如社交网络）。

五、对比与总结 💼

1. 核心差异对比 👞

2. 如何选择算法？👟

• Prim：适合邻接矩阵存储的稠密图（如完全图）。
• Kruskal：适合边较少的稀疏图（如社交网络）。

3. 常见误区 👠

• 负权边：两种算法均支持，不影响结果。
• 非连通图：需额外处理，否则无法生成完整 MST。