Minimum-Spanning-Tree

释义 Definition

最小生成树（MST）：在一个带权无向连通图中，选取一棵包含所有顶点的生成树，使得所有边的权重之和最小。（常见于图论与算法；也可写作 minimum spanning tree）

发音 Pronunciation (IPA)

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

例句 Examples

A minimum-spanning-tree connects all the nodes with the least total cost.
最小生成树以最小的总成本连接所有节点。

To optimize the network layout, the engineer computed a minimum-spanning-tree from the weighted graph and then added a few extra links for redundancy.
为优化网络布局，工程师从带权图中计算出一棵最小生成树，然后再添加少量额外链路以实现冗余。

词源 Etymology

该术语由三部分构成：minimum（最小的）+ spanning（“跨越/覆盖全部”的，来自 span “跨越”）+ tree（树，指图论中的“无环连通结构”）。合起来描述一种“覆盖所有顶点、且总权重最小的树形结构”。这一概念在20世纪中期的图论与运筹学发展中被系统化，常与 Kruskal、Prim 等算法并列出现。

相关词 Related Words

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

文学与经典作品 Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，《算法导论》）：在“最小生成树”章节系统讲解 MST、Kruskal 与 Prim 算法及其证明思路。
• The Algorithm Design Manual（Steven S. Skiena，《算法设计手册》）：以工程化视角介绍 MST 的典型应用场景与实现要点。
• Algorithms（Robert Sedgewick & Kevin Wayne，《算法》）：以示例与可视化思路讲解最小生成树与贪心策略。