青少年编程知识记录 - 最小生成树

2025年12月20日 14:19:12

最小生成树—基本概念

一、最小生成树核心概念

1. 基本定义

一个带权无向连通图的最小生成树，是指从该图中选择若干条边，构成一个包含图中所有顶点的树结构（无环、连通），且所有选中边的权值之和最小。

2. 关键性质

生成树的本质：包含图中全部n个顶点，且仅有n-1条边（保证无环且连通，增减一条边都会破坏树的性质）。
最小性：所有可能的生成树中，边权总和是最小的。
不唯一性：当图中存在多条相同权值的边时，可能存在多个不同结构但权值和相同的最小生成树。
适用范围：仅适用于无向连通图（非连通图只能求最小生成森林，即每个连通分量的最小生成树集合）。

二、两种经典求解算法

最小生成树的核心求解算法有两种：Kruskal 算法和 Prim 算法，二者思路不同但都能高效求得最优解。

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

1. 核心思想

“贪心选边，避环构建”：将所有边按权值从小到大排序，依次遍历每条边，若该边连接的两个顶点属于不同的连通分量（添加后不会形成环），则将其加入生成树；若属于同一连通分量（添加后会形成环），则跳过该边。重复此过程，直到生成树包含n-1条边。

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

并查集是 Kruskal 算法的关键数据结构，用于快速判断两个顶点是否属于同一连通分量，以及合并两个连通分量，操作的时间复杂度接近 O (1)（带路径压缩和按秩合并优化）。

3. 时间复杂度

边排序的时间复杂度：O (E log E)（E 为边数），这是算法的主导复杂度。
并查集操作的时间复杂度：O (E α(V))（α 为阿克曼函数的反函数，增长极慢，可视为常数）。
总体复杂度：O (E log E)，适合稀疏图（边数 E 远小于 V²，V 为顶点数）。

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

1. 核心思想

“贪心选点，逐步扩张”：从任意一个起始顶点出发，维护一个 “已加入生成树” 的顶点集合，每次从 “集合内顶点” 与 “集合外顶点” 的所有边中，选择权值最小的那条边，将对应的集合外顶点加入生成树。重复此过程，直到所有顶点都被加入生成树（此时已选n-1条边）。

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

使用最小堆（C++ 中priority_queue默认是最大堆，需手动调整为最小堆）可以高效获取 “当前最小权值的跨集合边”，避免暴力遍历所有边，优化时间复杂度。

3. 时间复杂度

未优化（暴力找最小边）：O (V²)，适合稠密图（边数 E 接近 V²）。
优先队列优化：O (E log V)，兼顾稀疏图和稠密图，适用性更广。

三、算法选择指南

特性	Kruskal 算法	Prim 算法（优先队列优化）
核心思路	选边（避环）	选点（扩张）
数据结构依赖	并查集 + 边集合	优先队列 + 邻接表
时间复杂度	O(E log E)	O(E log V)
适用场景	稀疏图（E 较小）	稠密图（E 较大），兼顾稀疏图
实现复杂度	较简单（并查集需提前实现）	稍复杂（邻接表构建）
空间复杂度	O (E)（存储所有边）	O (V + E)（邻接表存储）

四、应用场景

网络搭建：如通信网络、公路 / 铁路网络、电力网络等，在连接所有节点的前提下，最小化建设成本（对应边权为建设费用）。
聚类分析：将数据点视为顶点，点间距离视为边权，最小生成树可用于划分聚类（移除权值较大的边，得到多个连通分量即为不同聚类）。
图像分割：将图像像素视为顶点，像素间的相似度 / 差异度视为边权，通过最小生成树实现图像的前景与背景分割。
路径规划：在分布式系统中，通过最小生成树构建高效的消息传递路径，减少通信开销。

.jztagtree{max-height:85vh;right:0px}.jzDown{top:10vh}.jztagtree li a{background-color:#448EF6}.jztagtree li a:before{border-right:10px solid #448EF6}.jztagtree li a:hover{background:#0045a6}.jztagtree li a:hover::before{border-right:10px solid #0045a6}

$("#jztoc").toc({content: ".single", headings: "h1,h2,h3"});