一、最小生成树核心概念

1. 基本定义

2. 关键性质

• 生成树的本质：包含图中全部n个顶点，且仅有n-1条边（保证无环且连通，增减一条边都会破坏树的性质）。

• 最小性：所有可能的生成树中，边权总和是最小的。

• 不唯一性：当图中存在多条相同权值的边时，可能存在多个不同结构但权值和相同的最小生成树。

• 适用范围：仅适用于无向连通图（非连通图只能求最小生成森林，即每个连通分量的最小生成树集合）。

二、两种经典求解算法

算法 1：Kruskal（克鲁斯卡尔）算法

1. 核心思想

2. 核心依赖：并查集（Union-Find）

3. 时间复杂度

• 边排序的时间复杂度：O (E log E)（E 为边数），这是算法的主导复杂度。

• 并查集操作的时间复杂度：O (E α(V))（α 为阿克曼函数的反函数，增长极慢，可视为常数）。

• 总体复杂度：O (E log E)，适合稀疏图（边数 E 远小于 V²，V 为顶点数）。

算法 2：Prim（普里姆）算法

1. 核心思想

2. 优化方式：优先队列（最小堆）

3. 时间复杂度

• 未优化（暴力找最小边）：O (V²)，适合稠密图（边数 E 接近 V²）。

• 优先队列优化：O (E log V)，兼顾稀疏图和稠密图，适用性更广。

三、算法选择指南

四、应用场景

1. 网络搭建：如通信网络、公路 / 铁路网络、电力网络等，在连接所有节点的前提下，最小化建设成本（对应边权为建设费用）。

2. 聚类分析：将数据点视为顶点，点间距离视为边权，最小生成树可用于划分聚类（移除权值较大的边，得到多个连通分量即为不同聚类）。

3. 图像分割：将图像像素视为顶点，像素间的相似度 / 差异度视为边权，通过最小生成树实现图像的前景与背景分割。

4. 路径规划：在分布式系统中，通过最小生成树构建高效的消息传递路径，减少通信开销。