Minimum Spanning Tree

定义 Definition

Minimum spanning tree（最小生成树）：在一个连通的加权无向图中，选择一组边把所有顶点连接起来、且不形成回路（是一棵“树”），并使这些边的总权重之和最小的生成树。常用于网络布线、聚类、路径规划等问题。（注：在不连通图中对应概念常称为“minimum spanning forest 最小生成森林”。）

发音 Pronunciation (IPA)

/ˌmɪnɪməm ˈspænɪŋ triː/

例句 Examples

A minimum spanning tree connects all nodes with the smallest total weight.
最小生成树用总权重最小的方式把所有节点连接起来。

Using Kruskal’s algorithm, we can build a minimum spanning tree for a weighted graph even when many edges share similar costs.
使用克鲁斯卡尔算法，即使许多边的代价相近，我们也能为加权图构建一棵最小生成树。

词源 Etymology

该术语由三部分组成：minimum（最小的）+ spanning（覆盖/连通所有顶点的）+ tree（树，指无环连通结构）。它源于图论与网络优化领域，用来描述“在覆盖所有顶点的前提下，使边权总和最小的树形连接结构”。

相关词 Related Words

• Graph
• Vertex
• Edge
• Weight
• Spanning Tree
• Kruskal’s Algorithm
• Prim’s Algorithm
• Greedy Algorithm
• Connected Graph

文学与经典著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：以最小生成树为经典“贪心算法”应用，系统讲解 Prim 与 Kruskal 算法及其正确性思路。
• Algorithm Design（Kleinberg & Tardos）：用最小生成树说明贪心策略与交换论证（exchange argument）的证明方法。
• The Algorithm Design Manual（Skiena）：以工程视角介绍最小生成树的用途、实现要点与常见变体。
• Network Flows: Theory, Algorithms, and Applications（Ahuja, Magnanti, Orlin）：在网络优化背景下讨论与最小生成树相关的算法与应用场景。